DocumentCode :
807297
Title :
Topological via minimization revisited
Author :
Sarrafzadeh, M. ; Lee, D.T.
Author_Institution :
Dept. of Electr. Eng. & Comput. Sci., Northwestern Univ., Evanston, IL, USA
Volume :
40
Issue :
11
fYear :
1991
fDate :
11/1/1991 12:00:00 AM
Firstpage :
1307
Lastpage :
1312
Abstract :
The topological via minimization problem in a two-layer environment is considered. A set of n two-terminal nets in a bounded region is given. The authors attempt to find a homotopy to assign nets to distinct layers so that no two nets on the same layer cross each other and the number of vias is minimized. A recursive approach in which an optimal solution to a two-sided channel routing problem is used as a basis is used to solve this problem optimally. The notion of partition number K of a circle graph is introduced, and the total running time of the via minimization algorithm is shown to be O((n/K)2K-2 log (n/K)), where n is the total number of nets
Keywords :
circuit layout CAD; graph theory; bounded region; circle graph; homotopy; optimal solution; partition number; topological via minimization problem; two-layer environment; two-sided channel routing problem; two-terminal nets; Application software; Availability; Computational complexity; Computational efficiency; Degradation; Distributed computing; Fault tolerant systems; Performance evaluation; Routing; Stochastic processes;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/12.102839
Filename :
102839
Link To Document :
بازگشت