Optimal Three-Layer Channel Routing
- 1 May 1984
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-33 (5), 427-437
- https://doi.org/10.1109/tc.1984.1676459
Abstract
In this paper we show that any channel routing problem of density d involving only two-terminal nets can always be solved in the knock-knee mode in a channel of width equal to the density d with three conducting layers. An algorithm is described which produces in time O(n log n) (in its simplest implementation) a layout of n nets with the following properties: 1) it has minimal width d; 2) it can be realized with three layers; 3) it has at most 3n vias; 4) any two wires share at most four grid points. Without sacrificing any of the above properties (but possibly obtaining slightly longer wires), the layout algorithm can be modified to run in time θ(n).Keywords
This publication has 7 references indexed in Scilit:
- A linear-time algorithm for a special case of disjoint set unionPublished by Association for Computing Machinery (ACM) ,1983
- Provably Good Channel Routing AlgorithmsPublished by Springer Nature ,1981
- Optimal wiring between rectanglesPublished by Association for Computing Machinery (ACM) ,1981
- Graph TheoryPublished by Springer Nature ,1979
- Preserving order in a forest in less than logarithmic time and linear spaceInformation Processing Letters, 1977
- A “Dogleg” channel routerPublished by Association for Computing Machinery (ACM) ,1976
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975