On the Difficulty of Manhattan Channel Routing

Ronald I. Greenberg; Joseph JaJa; Sridhar Krishnamurthy

doi:10.1016/0020-0190(92)90214-G

On the Difficulty of Manhattan Channel Routing

Ronald I. Greenberg, Joseph JaJa, Sridhar Krishnamurthy

Department of Computer Science

Research output: Contribution to journal › Article › peer-review

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+Omega(sqrt(n)) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.

Original language	American English
Journal	Computer Science: Faculty Publications and Other Works
Volume	44
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(92)90214-G
State	Published - Dec 1 1992

Keywords

VLSI channel routing
combinatorial problems
computational complexity
lower bounds

Disciplines

Computer Sciences
Theory and Algorithms
VLSI and Circuits, Embedded and Hardware Systems

Access to Document

10.1016/0020-0190(92)90214-GLicense: Unspecified

On the Difficulty of Manhattan Channel RoutingFinal published version, 219 KBLicense: Unspecified

http://dx.doi.org/10.1016/0020-0190(92)90214-G

Cite this

@article{98b5aca1fcd64c8a993b73df91463014,

title = "On the Difficulty of Manhattan Channel Routing",

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+Omega(sqrt(n)) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.",

keywords = "VLSI channel routing, combinatorial problems, computational complexity, lower bounds",

author = "Greenberg, \{Ronald I.\} and Joseph JaJa and Sridhar Krishnamurthy",

note = "Information Processing Letters, Volume 44, Issue 5, 21 December 1992, Pages 281–284.",

year = "1992",

month = dec,

day = "1",

doi = "10.1016/0020-0190(92)90214-G",

language = "American English",

volume = "44",

journal = "Computer Science: Faculty Publications and Other Works",

number = "5",

}

TY - JOUR

T1 - On the Difficulty of Manhattan Channel Routing

AU - Greenberg, Ronald I.

AU - JaJa, Joseph

AU - Krishnamurthy, Sridhar

N1 - Information Processing Letters, Volume 44, Issue 5, 21 December 1992, Pages 281–284.

PY - 1992/12/1

Y1 - 1992/12/1

N2 - 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+Omega(sqrt(n)) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.

AB - 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+Omega(sqrt(n)) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.

KW - VLSI channel routing

KW - combinatorial problems

KW - computational complexity

KW - lower bounds

UR - https://ecommons.luc.edu/cs_facpubs/102

U2 - 10.1016/0020-0190(92)90214-G

DO - 10.1016/0020-0190(92)90214-G

M3 - Article

VL - 44

JO - Computer Science: Faculty Publications and Other Works

JF - Computer Science: Faculty Publications and Other Works

IS - 5

ER -

On the Difficulty of Manhattan Channel Routing

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Cite this