On the Difficulty of Manhattan Channel Routing

Ronald I. Greenberg, Joseph F. JáJá, Sridhar Krishnamurthy

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+Ω(n)<math><mtext>d+Ω(</mtext><mtext>n</mtext><mtext>)</mtext></math> tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.
BibTeX
@inproceedings{greenberg1992difficulty,
  author = {Ronald I. Greenberg and Joseph F. JáJá and Sridhar Krishnamurthy},
  title = {{On the Difficulty of Manhattan Channel Routing}},
  booktitle = {Inf. Process. Lett},
  year = {1992},
  url = {https://openreview.net/forum?id=9bJrQe6QB5},
}

Loading related content...

Figure