@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}
}
