An efficient layer assignment algorithm for gridless switchbox routing
作者： A. Pitak , C. Lursinsap
关键词:
摘要: A graph-theoretic algorithm is presented for the layer assignment and via minimization of a gridless switchbox routing. concept called propagation used to facilitate vias. The time complexity proposed O( n log + K ), where number routing wire segments in layout maximum vias that can occur. approach achieves minimum several difficult problems
sci-hub.se 参考文章(15)
Bentley, Ottmann, Algorithms for Reporting and Counting Geometric Intersections IEEE Transactions on Computers. ,vol. 28, pp. 643- 647 ,(1979) , 10.1109/TC.1979.1675432
M. J. Ciesielski, E. Kinnen, An Optimum Layer Assignment for Routing in ICs and PCBs design automation conference. pp. 733- 737 ,(1981) , 10.5555/800073.802387
J.P. Cohoon, P.L. Heck, BEAVER: a computational-geometry-based tool for switchbox routing IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 7, pp. 684- 697 ,(1988) , 10.1109/43.3208
Chi-Ping Hsu, Minimum-Via Topological Routing IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 2, pp. 235- 246 ,(1983) , 10.1109/TCAD.1983.1270041
M. Burstein, R. Pelavin, Hierarchical Wire Routing IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 2, pp. 223- 234 ,(1983) , 10.1109/TCAD.1983.1270040
N. J. Naclerie, S. Masuda, K. Nakajima, Via minimization for gridless layouts 24th ACM/IEEE conference proceedings on Design automation conference - DAC '87. pp. 159- 165 ,(1987) , 10.1145/37888.37912
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
KC Chang, HC Du, None, A Preprocessor for the Via Minimization Problem design automation conference. pp. 702- 707 ,(1986) , 10.5555/318013.318144
KC Chang, DH-C Du, None, Efficient Algorithms for Layer Assignment Problem IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. ,vol. 6, pp. 67- 78 ,(1987) , 10.1109/TCAD.1987.1270247
Akihiro Hashimoto, James Stevens, Wire routing by optimizing channel assignment within large apertures design automation conference. pp. 155- 169 ,(1971) , 10.1145/800158.805069