Chicago Journal of Theoretical Computer Science

Volume 1996

Article 6

Published by MIT Press. Copyright 1996 Massachusetts Institute of Technology.

Your institution may already be a subscriber to CJTCS. If not, please subscribe for legitimate access to all journal articles.

Manhattan Channel Routing is NP-Complete under Truly Restricted Settings

Martin Middendorf (Universität Karlsruhe)
30 December 1996

Settling an open problem that is over ten years old, we show that Manhattan channel routing---with doglegs allowed---is NP-complete when all nets have two terminals. This result fills the gap left by Szymanski, who showed the NP-completeness for nets with four terminals. Answering a question posed by Schmalenbach and Greenberg, Jájá, and Krishnamurty, we prove that the problem remains NP-complete if in addition the nets are single-sided and the density of the bottom nets is at most one. Moreover, we show that Manhattan channel routing is NP-complete if the bottom boundary is irregular and there are only 2-terminal top nets. All of our results also hold for the restricted Manhattan model where doglegs are not allowed.

DOI: 10.4086/cjtcs.1996.006
[] Article 5 [] Volume 1997, Article 1
[back] Volume 1996 [back] Published articles
[CJCTS home]

Last modified: 24 March 1997