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

AbstractThere 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 [36] we presented some more recent ones, including:1. a linear time channel routing algorithm in the unconstrained two-layer model;2. a linear time switchbox routing algorithm in the unconstrained multilayer model; and3. a linear time solution of the so called gamma routing problem in 2Mm.(This latter means that all the terminals to be interconnected are situated at two adjacent sides of a rectangular routing area, thus forming a Γ shape. Just like channel routing, it is a special case of switchbox routing, and contains single row routing as a special case.)In the present survey talk we also mention some results from the last three years, including4. some negative results (NP-completeness) in the multilayer Manhattan model and a channel routing algorithm if the number of layers is even;5. an interesting relation between channel routing and multiprocessor scheduling; and6. some improvements of 1–3 above.We present the (positive and negative) results in a systematic way, taking into account two hierarchies, namely that of geometry (what to route) and technology (how to route) at the same time