Fast algorithm for optimal layer assignment

Abstract

[[abstract]]Given the geometry of wires for interconnections, the authors want to assign two conducting layers to the segments of these wires so that the number of vias required is minimized. This layer assignment problem, also referred to as the via minimization problem, has been formulated as finding a maximum cut of a planar graph. The authors propose a novel algorithm for optimal layer assignment under a general model where the planar graph has real-valued edge weights. The time complexity of the proposed algorithm is O(n3/2 log n) where n is the number of wire-segment clusters in a given layout. In contrast, all existing optimal algorithms for layer assignment have the time complexity of O(n3).[[fileno]]2030218030007[[department]]資訊工程學

This publication has 14 references indexed in Scilit:

Fast algorithm for optimal layer assignment
Published by Institute of Electrical and Electronics Engineers (IEEE) ,2003
Via minimization for gridless layouts
Published by Association for Computing Machinery (ACM) ,1987
Planar Multicommodity Fows, Maximum Matchings and Negative Cycles
SIAM Journal on Computing, 1986
An Unconstrained Topological Via Minimization Problem for Two-Layer Routing
IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1984
A graph-theoretic via minimization algorithm for two-layer printed circuit boards
IEEE Transactions on Circuits and Systems, 1983
Priority queues with variable priority and an O(EV log V) algorithm for finding a maximal weighted matching in general graphs
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1982
An Optimum Layer Assignment for Routing in ICs and PCBs
Published by Institute of Electrical and Electronics Engineers (IEEE) ,1981
Applications of a Planar Separator Theorem
SIAM Journal on Computing, 1980
A Separator Theorem for Planar Graphs
SIAM Journal on Applied Mathematics, 1979
Efficient Planarity Testing
Journal of the ACM, 1974