Information Processing Letters
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+Omega(sqrt(n)) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.
Information Processing Letters, Volume 44, Issue 5, 21 December 1992, Pages 281–284.
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.
© Elsevier, 1992.
Author Posting. © Elsevier, 1992. This article is posted here by permission of Elsevier for personal use, not for redistribution. The article was published in Information Processing Letters, Volume 44, Issue 5, 1992, http://dx.doi.org/10.1016/0020-0190(92)90214-G