DocumentCode
916604
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
Volume
37
Issue
6
fYear
1988
fDate
6/1/1988 12:00:00 AM
Firstpage
721
Lastpage
727
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;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.2210
Filename
2210
Link To Document