Optimal two-terminal a-b wire routing
作者： J.P. Cohoon , D.S. Richards
DOI: 10.1016/0167-9260(88)90017-X
关键词:
摘要: Abstract Wire routing problems have received a great deal of attention over the past two decades. However, worst-case performance classical techniques such as maze and line search routers is still lower-bounded by number grid points available for routing. This typically quite large theoretically independent circuit medium obstacles (i.e. module boundaries previously laid wires). We consider here several minimum bend length graduated difficulty. For these we suggest methods whose running times are dependent upon in region, m, rather than size underlying grid.
elsevier.com
sci-hub.se 参考文章(34)
Günter Werner, Albrecht Hübler, Reinhard Klette, Shortest Path Algorithms for Graphs of Restricted In-Degree and Out-Degree. Journal of Automata, Languages and Combinatorics. ,vol. 18, pp. 141- 151 ,(1982)
S.H. Whitesides, Computational Geometry and Motion Planning Machine Intelligence and Pattern Recognition. ,vol. 2, pp. 377- 427 ,(1985) , 10.1016/B978-0-444-87806-9.50019-0
Glenn E. Wangdahl, Stephen M. Pollock, John B. Woodward, MINIMUM-TRAJECTORY PIPE ROUTING Journal of Ship Research. ,vol. 18, pp. 46- 49 ,(1974) , 10.5957/JSR.1974.18.1.46
Koichi Mikami, Kinya Tabuchi, A computer program for optimal routing of printed circuit conductors. ifip congress. pp. 1475- 1478 ,(1968)
Bentley, Wood, An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles IEEE Transactions on Computers. ,vol. 29, pp. 571- 577 ,(1980) , 10.1109/TC.1980.1675628
Bentley, Ottmann, Algorithms for Reporting and Counting Geometric Intersections IEEE Transactions on Computers. ,vol. 28, pp. 643- 647 ,(1979) , 10.1109/TC.1979.1675432
F. Rubin, The Lee Path Connection Algorithm IEEE Transactions on Computers. ,vol. 23, pp. 907- 914 ,(1974) , 10.1109/T-C.1974.224054
Y. F. Wu, P. Widmayer, C. K. Wong, A faster approximation algorithm for the Steiner problem in graphs Acta Informatica. ,vol. 23, pp. 223- 229 ,(1986) , 10.1007/BF00289500
Witold Lipski, An O(n log n) Manhattan path algorithm Information Processing Letters. ,vol. 19, pp. 99- 102 ,(1984) , 10.1016/0020-0190(84)90105-4
F. O. Hadlock, A shortest path algorithm for grid graphs Networks. ,vol. 7, pp. 323- 334 ,(1977) , 10.1002/NET.3230070404