%0 Journal Article
%J Information Processing Letters
%D 1992
%T On the difficulty of Manhattan channel routing
%A Greenberg,Ronald
%A JaJa, Joseph F.
%A Krishnamurthy,Sridhar
%K combinatorial problems
%K computational complexity
%K lower bounds
%K VLSI channel routing
%X 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.
%B Information Processing Letters
%V 44
%P 281 - 284
%8 1992/12/21/
%@ 0020-0190
%G eng
%U http://www.sciencedirect.com/science/article/pii/002001909290214G
%N 5
%R 10.1016/0020-0190(92)90214-G