首页    期刊浏览 2024年10月05日 星期六
登录注册

文章基本信息

  • 标题:Manhattan Channel Routing is NP-complete Under Truly Restricted Settings
  • 本地全文:下载
  • 作者:Martin Middendorf
  • 期刊名称:Chicago Journal of Theoretical Computer Science
  • 印刷版ISSN:1073-0486
  • 出版年度:1996
  • 卷号:1996
  • 出版社:MIT Press ; University of Chicago, Department of Computer Science
  • 摘要:

    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.

国家哲学社会科学文献中心版权所有