Title :
On two-dimensional via assignment for single-row routing
Author :
Du, H.C. ; Ibarra, Oscar H. ; Naveda, J. Fernando
Author_Institution :
Dept. of Comput. Sci., Minnesota Univ., Minneapolis, MN, USA
fDate :
6/1/1988 12:00:00 AM
Abstract :
The authors study the via assignment problem when vias are allowed to appear rowwise as well as columnwise. Previously they proved that the problem belongs to the class of NP-hard problems and therefore it is unlikely that polynomial-time algorithms exist for solving the problem. Two heuristics (HEU1 and HEU2) to solve the problem were proposed. HEU1 splits the nets before any routing is done while HEU2 assigns the nets alternately to via rows and via columns. Here they modify HEU2 so that the side of the board to which the nets are assigned first for connection is selected according to a desired ratio of board width to height
Keywords :
circuit layout CAD; directed graphs; printed circuits; HEU1; HEU2; NP-hard problems; polynomial-time algorithms; single-row routing; two-dimensional via assignment; Computer science; Fabrication; Heuristic algorithms; Integrated circuit interconnections; Nonhomogeneous media; Pins; Printed circuits; Routing; Wires; Wiring;
Journal_Title :
Computers, IEEE Transactions on
