On the Difficulty of Manhattan Channel Routing

Authors

Ronald I. Greenberg, Loyola University ChicagoFollow
Joseph JaJa
Sridhar Krishnamurthy

Document Type

Article

Publication Date

12-1992

Publication Title

Information Processing Letters

Volume

44

Issue

5

Pages

281-284

Publisher Name

Elsevier

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+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.

Comments

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

Recommended Citation

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.

Copyright Statement

© Elsevier, 1992.