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.

Abstract

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.

• Preformatted versions of the article
  • DVI (117,580 bytes)
  • PostScript (287,272 bytes)
  • PDF (249,760 bytes)
  • Audio by AsTeR (to appear)
• Source materials for custom formatting
  • LaTeX (cj96-06.tex, 67,014 bytes)
  • BIBTeX (cj96-06.bib, 2,791 bytes)
  • Parameter settings for custom formatting (cjropts.tex, 164 bytes)
  • Self citation in BIBTeX (289 bytes)
• Online discussion
• Instructions for Readers

DOI: 10.4086/cjtcs.1996.006

---

Article 5 Volume 1997, Article 1
Volume 1996 Published articles

Last modified: 24 March 1997