IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1989 · 73 citations · 14 references
Natural SciencesComputer ScienceMathematicsAlgorithmsOptimizationTopologyCombinatorial OptimizationInteger ProgrammingLayout OptimizationRoutingRouting AlgorithmsTopology OptimizationMinimizationRouting ProblemsTopology DesignVery-large-scale IntegrationVia Optimization
A topological via minimization problem in a two-layer routing environment is examined. The problem of minimizing the number of vias needed to route n two-terminal nets in a bounded routing region is shown to be NP-hard. However, in the case of a two-shore routing region, the topological via minimization problem can be solved in O(n/sup 2/ log n) time. As a basis for the algorithm, a two-chain maximum dominance problem, which is of interest in its own right, is considered, and its applications to other very large-scale integration layout problems are shown.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
14
Planar Formulae and Their Uses
David Lichtenstein · SIAM Journal on Computing · 1982 · 754 citations
New lower bound techniques for VLSI
Frank Thomson Leighton · Theory of Computing Systems · 1984 · 179 citations
Optimal layer assignment for interconnect
Ron Y. Pinter · 1984 · 112 citations
Natural Sciences, Computer Science, Electrical Engineering +13