@article {14997, title = {On the difficulty of Manhattan channel routing}, journal = {Information Processing Letters}, volume = {44}, year = {1992}, month = {1992/12/21/}, pages = {281 - 284}, abstract = {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.}, keywords = {combinatorial problems, computational complexity, lower bounds, VLSI channel routing}, isbn = {0020-0190}, doi = {10.1016/0020-0190(92)90214-G}, url = {http://www.sciencedirect.com/science/article/pii/002001909290214G}, author = {Greenberg,Ronald and JaJa, Joseph F. and Krishnamurthy,Sridhar} }