Some polynomially solvable subcases of the detailed routing problem in VLSI design Original Research Article

There are plenty of NP-complete problems in very large scale integrated design, like channel routing or switchbox routing in the two-layer Manhattan model (2Mm, for short). However, there are quite a few polynomially solvable problems as well. Some of them (like the single row routing in 2Mm) are “classical” results; in a past survey we presented some more recent ones, including: