Minimum-Via Topological Routing
- 1 October 1983
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 2 (4) , 235-246
- https://doi.org/10.1109/tcad.1983.1270041
Abstract
A new approach to the two-dimensional routing utilizing two layers is proposed. It consists of two major steps, topological routing and geometrical mapping. This paper describes the topological routing algorithm in detail. Based on a circle graph representation of the net intersection information of the routing problem, a maximal set of nets that can be routed without vias are selected. The layer assignments for the selected nets are determined by a global analysis so that the total number of vias needed is minimum. The layer assignment problem turns out to be a maximum-cut problem on an edge-weighted graph and we developed a greedy algorithm for it. According to the layer assignments, the detailed topological routes are then generated.Keywords
This publication has 8 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- A new two-dimensional routing algorithmPublished by Association for Computing Machinery (ACM) ,1982
- Comments on F. Hadlock’s Paper: “Finding a Maximum Cut of a Planar Graph in Polynomial Time”SIAM Journal on Computing, 1977
- Finding a Maximum Cut of a Planar Graph in Polynomial TimeSIAM Journal on Computing, 1975
- Algorithms for a maximum clique and a maximum independent set of a circle graphNetworks, 1973
- Permutation Graphs and Transitive GraphsJournal of the ACM, 1972
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal GraphSIAM Journal on Computing, 1972
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972