On the Difficulty of Manhattan Channel Routing
Lists
Only you see this
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...