Single Row Routing on Multilayers

摘要

A common problem in VLSI is automating the routing of wires between pins 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 line. To prevent electrical interference, the wires are laid out in tracks parallel to the row of pins and distinct wires are prohibited from crossing. Formally, the single row routing problem, known to be NP-complete, involves determining the feasibility of any wiring in the minimum number of tracks. When wires may be routed on more than one layer the problem of determining the feasibility of a wiring in a minimum number of layers but with an arbitrary number of parallel tracks is NP-complete. A long-standing open problem has been the complexity of the single row routing problem on multilayers when the number of parallel tracks per layer is fixed. We show that this version of the problem is also NP-complete.