CJTCS Volume 1996 Article 6
Manhattan Channel Routing is NP-Complete under Truly Restricted Settings
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)
- 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)
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/up.gif)
![[]](http://www.cs.uchicago.edu/publications/cjtcs/art/down.gif)
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
![[back]](http://www.cs.uchicago.edu/publications/cjtcs/art/back.gif)
![[CJCTS home]](http://www.cs.uchicago.edu/publications/cjtcs/art/logo_www_button.gif)
Last modified: 24 March 1997