Name
Abstract | ||
|---|---|---|
A theoretical study which allows determination of the minimum number of vias for realizable multilayer channel routing under a topological model is presented. The theory is sufficiently general to solve a variety of problems under different technological constraints, e.g. VLSI multilayer switchbox and channel routing, through-hole printed circuit board (PCB) channels, and single-layer routing. Topological routing is concerned with wire intersection but not area, zero-width wires and zero-area vias being assumed. Unconstrained via minimization (UVM) is not constrained to a prerouted topology. This paper presents restrictive cases of UVM, finding most to be NP-hard, but the case resulting from constraints of traditional switchbox or channel routing to be solvable in O(kn2), where k is the maximum number of pins of a net layer and n is the number of pins. The minimum number of vias for various switchbox and channel routing benchmarks are reported |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1109/43.59073 | Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions |
Keywords | DocType | Volume |
VLSI,circuit layout CAD,computational complexity,network topology,printed circuit design,NP-hard,UVM,VLSI,benchmarks,channel routing,multilayer switchbox,net layer,printed circuit board,single-layer routing,topological multilayer routing,unconstrained via minimisation,vias,wire intersection | Journal | 9 |
Issue | ISSN | Citations |
9 | 0278-0070 | 8 |
PageRank | References | Authors |
1.44 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Matthias F. M. Stallmann | 1 | 166 | 19.38 |
| Thomas A. Hughes | 2 | 8 | 1.44 |
| Wentai Liu | 3 | 717 | 135.62 |