Title :
On topological via minimization and routing
Author :
Hossain, Moazzem ; Sherwani, Naveed A.
Author_Institution :
Dept. of Comput. Sci., Western Michigan Univ., Kalamazoo, MI, USA
Abstract :
The authors consider the topological via minimization problem in a bounded region. The problem is known to be NP-complete. An approximation algorithm is proposed for this problem, which solves the two-layer topological via minimization problem in a bounded region with at most 0.25m* more vias than the optimal number of vias, where m* is the size of the maximum two-planar subset of nets for the given problem. A graph-theoretic heuristic algorithm is also proposed to obtain a geometric routing from a topological solution.<>
Keywords :
circuit layout CAD; computational complexity; heuristic programming; NP-complete; approximation algorithm; geometric routing; graph-theoretic heuristic algorithm; routing; topological via minimization; Approximation algorithms; Circuit synthesis; Computer science; Iterative algorithms; Minimization methods; Packaging; Polynomials; Routing; Solids; Very large scale integration;
Conference_Titel :
Computer-Aided Design, 1991. ICCAD-91. Digest of Technical Papers., 1991 IEEE International Conference on
Conference_Location :
Santa Clara, CA, USA
Print_ISBN :
0-8186-2157-5
DOI :
10.1109/ICCAD.1991.185324
