DocumentCode
1955346
Title
A new algorithm for topological routing and via minimization
Author
Xiong Xiao-Ming
Author_Institution
Dept. of Electr. Eng. & Comput. Sci., California Univ., Berkeley, CA, USA
fYear
1988
fDate
7-10 Nov. 1988
Firstpage
410
Lastpage
413
Abstract
A topological method for two-layer routing of printed circuit boards and VLSI chips is presented. The primary criterion is via minimization. Multiterminal nets and multiple wires are allowing to intersect at any via. After topological routing, the via minimization problem is then formulated as a (0, 1) linear programming problem and solved. The time and space complexities of the algorithm are O(n/sup 2/) and O(n+k), respectively, where n is the number of terminals in the routing region and k is the total number of cross points and via candidates.<>
Keywords
circuit layout CAD; integer programming; linear programming; minimisation; network topology; (0, 1) linear programming problem; VLSI chips; algorithm space complexity; algorithm time complexity; cross points; intersection; multiple wires; multiterminal nets; printed circuit boards; terminals; topological routing; two-layer routing; via minimization; Minimization methods; Niobium; Routing; Terminology; Wires;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer-Aided Design, 1988. ICCAD-88. Digest of Technical Papers., IEEE International Conference on
Conference_Location
Santa Clara, CA, USA
Print_ISBN
0-8186-0869-2
Type
conf
DOI
10.1109/ICCAD.1988.122539
Filename
122539
Link To Document