TY - JOUR
T1 - On the difficulty of Manhattan channel routing
JF - Information Processing Letters
Y1 - 1992
A1 - Greenberg,Ronald
A1 - JaJa, Joseph F.
A1 - Krishnamurthy,Sridhar
KW - combinatorial problems
KW - computational complexity
KW - lower bounds
KW - VLSI channel routing
AB - We show that channel routing in the Manhattan model remains difficult even when all nets are single-sided. Given a set of n single-sided nets, we consider the problem of determining the minimum number of tracks required to obtain a dogleg-free routing. In addition to showing that the decision version of the problem isNP-complete, we show that there are problems requiring at least d+Ω(n) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.
VL - 44
SN - 0020-0190
UR - http://www.sciencedirect.com/science/article/pii/002001909290214G
CP - 5
M3 - 10.1016/0020-0190(92)90214-G
ER -