Title :
Complexity of Single-Layer Routing
Author_Institution :
Department of Computer and Information Science, Indiana University-Purdue University
fDate :
3/1/1984 12:00:00 AM
Abstract :
The problem of routing wires between pairs of terminals over a two-dimensional grid is shown to be NP-complete. Actually, the stronger result of routing over any planar graph with no vertex having degree greater than 3 is shown to be NP-complete.
Keywords :
NP-completeness; VLSI design; planar graphs; single-layer routing; vertex disjoint paths; Bipartite graph; Design automation; Information science; Joining processes; Nonhomogeneous media; Printed circuits; Routing; Very large scale integration; Wires; Wiring; NP-completeness; VLSI design; planar graphs; single-layer routing; vertex disjoint paths;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1984.1676428
