IEEE Transactions on Computers · 1988 · 46 citations · 15 references
EngineeringComputer EngineeringElectrical EngineeringAlgorithmsInterconnection NetworksOptimizationAssignment ProblemsCombinatorial OptimizationInterconnect DesignNetwork OptimizationRoutingRouting AlgorithmsInterconnect AssignmentInterconnect Layout OptimizationInterconnect RoutingLayer AssignmentMinimizationRouting ProblemsThree-dimensional Integrated Circuit RoutingVia Optimization
The layer assignment problem for interconnect is the problem of determining which layers should be used for wiring the signal nets so that the number of vias is minimized. The problem is often referred to as the via minimization problem. The problem is considered for three-layer routing, concentrating on one version called the constrained via minimization (CVM3) problem. It is shown that the CVM3 problem is NP-complete and a heuristic algorithm is proposed. The experimental results show that the proposed algorithm is efficient and generates fairly good solutions.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
15
The Complexity of Near-Optimal Graph Coloring
M. R. Garey, David S. Johnson · Journal of the ACM · 1976 · 326 citations · Full text
Graph theory with application to engineering and computer science
Narsing Deo, Farrokh Ghahremaninejad, Amin Zeraatkar et al. · 1995 · 206 citations
Optimal layer assignment for interconnect
Ron Y. Pinter · 1984 · 112 citations
Natural Sciences, Computer Science, Electrical Engineering +13