DocumentCode
1181863
Title
Via assignment problem in multilayer printed circuit board
Author
Ting, Benjamin S. ; Kuh, Ernest S. ; Sangiovanni-Vincentelli, Alberto
Volume
26
Issue
4
fYear
1979
fDate
4/1/1979 12:00:00 AM
Firstpage
261
Lastpage
272
Abstract
In the routing of a multilayer printed circuit board an important phase is the via assignments. In this paper, the via assignment problem is given a graph theoretic formulation. Some related optimization problems are proven to belong to a particular class of hard combinatorial problem: the class of nondeterministic polynomial (NP)-complete problems. This result suggests that the only way to solve efficiently the optimization problems is to introduce heuristic algorithms. Hence, some heuristic algorithms a proposed and their performances are evaluated.
Keywords
Graph theory and combinatorics; Layout; Aerospace electronics; Conductors; Integrated circuit interconnections; Laboratories; Minimization; Nonhomogeneous media; Pins; Printed circuits; Routing; Wires;
fLanguage
English
Journal_Title
Circuits and Systems, IEEE Transactions on
Publisher
ieee
ISSN
0098-4094
Type
jour
DOI
10.1109/TCS.1979.1084634
Filename
1084634
Link To Document