Compact Channel Routing of Multiterminal Nets
作者： M. Sarrafzadeh , F.P. Preparata
DOI: 10.1016/S0304-0208(08)73111-6
关键词: Net (mathematics) 、 Communication channel 、 Routing (electronic design automation) 、 Mathematics 、 Topology 、 Optimal methods 、 Theoretical computer science 、 Novel technique
摘要: In this paper we describe a novel technique for solving the channel routing problem of multiterminal nets. The layout is produced column-by-column in left-to-right scan: number t used tracks satisfies bound δ ≤ δ+α(0 δ−1), where density problem. behaves equivalently to known optimal methods two-terminal net problems. For with C columns and n nets, algorithms run time O(Clogn) produces layouts that are provably wirable three layers.
sci-hub.se 参考文章(3)
Ronald L. Rivest, Alan E. Baratz, Gary Miller, Provably Good Channel Routing Algorithms VLSI Systems and Computations. pp. 153- 159 ,(1981) , 10.1007/978-3-642-68402-9_18
Preparata, Lipski, Optimal Three-Layer Channel Routing IEEE Transactions on Computers. ,vol. 33, pp. 427- 437 ,(1984) , 10.1109/TC.1984.1676459
Ronald L. Rivest, Charles M. Fiduccia, Charles M. Fiduccia, A "Greedy" Channel Router design automation conference. pp. 418- 424 ,(1982) , 10.5555/800263.809239