IEEE Transactions on Computers · 1984 · 100 citations · 5 references
EngineeringComputer ScienceElectrical EngineeringCircuit TheoryInterconnection NetworksOptimizationChannel DesignCombinatorial OptimizationNetwork OptimizationRoutingRouting AlgorithmsRouting ArchitectureChannel RoutingDensityMultilayer RoutingNetwork Design ProblemsThree-dimensional Integrated Circuit RoutingTopology Synthesis
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).
5
D.N. Deutsch · 1976 · 397 citations
Engineering, Computer Engineering, Electrical Engineering +13
Optimal wiring between rectangles
Danny Dolev, Kevin Karplus, Alan Siegel et al. · 1981 · 68 citations