SINGLE ROW ROUTING ON MULTILAYERS

A common problem in VLSI is automating the routing of wires between pi ns in a circuit. Several specifications of the routing problem exist. One class of these problems, known as the single row routing problem, involves routing wires when the pins are laid out along a straight lin e. To prevent electrical interference, the wires are laid out in track s parallel to the row of pins and distinct wires are prohibited from c rossing. Formally, the single row routing problem, known to be NP-comp lete, involves determining the feasibility of any wiring in the minimu m number of tracks. When wires may be routed on more than one layer th e problem of determining the feasibility of a wiring in a minimum numb er of layers but with an arbitrary number of parallel tracks is NP-com plete. A long-standing open problem has been the complexity of the sin gle row routing problem on multilayers when the number of parallel tra cks per layer is fixed. We show that this version of the problem is al so NP-complete. (C) 1995 Academic Press, Inc.