RIVER ROUTING EVERY WHICH WAY, BUT LOOSE.

Richard Cole; Alan Siegel

doi:10.1109/sfcs.1984.715902

RIVER ROUTING EVERY WHICH WAY, BUT LOOSE.

Richard Cole, Alan Siegel

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The authors treat the DRH (detailed routing given a homotopy) problem, which deals with the placement of a set of rectangular modules within a bounding box, numbered terminals on the modules' boundaries, and a homotopy (rough routing) specification for each net. The problem is to determine whether there is a one-layer detailed routing for this configuration that conforms to the given homotopy. It is shown how to solve DRH in O(n plus m log m plus D(m)) operations. The solution uses n plus m log m homotopy queries that are elementary; they are answerable based solely on local properties of modules, terminals, and wire connections. In addition, O(m) more complex queries are needed, and these are represented in the D(m) term. These queries must account for the total number of crossings occurring for selected test segments.

Original language	English (US)
Title of host publication	Annual Symposium on Foundations of Computer Science (Proceedings)
Publisher	IEEE
Pages	65-73
Number of pages	9
ISBN (Print)	081860591X, 9780818605918
DOIs	https://doi.org/10.1109/sfcs.1984.715902
State	Published - 1984

Publication series

Name	Annual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)	0272-5428

ASJC Scopus subject areas

Hardware and Architecture

Access to Document

10.1109/sfcs.1984.715902

Fingerprint Dive into the research topics of 'RIVER ROUTING EVERY WHICH WAY, BUT LOOSE.'. Together they form a unique fingerprint.

Cite this

@inproceedings{b92216b2fd1140e19eadd0bf28731f88,

title = "RIVER ROUTING EVERY WHICH WAY, BUT LOOSE.",

abstract = "The authors treat the DRH (detailed routing given a homotopy) problem, which deals with the placement of a set of rectangular modules within a bounding box, numbered terminals on the modules' boundaries, and a homotopy (rough routing) specification for each net. The problem is to determine whether there is a one-layer detailed routing for this configuration that conforms to the given homotopy. It is shown how to solve DRH in O(n plus m log m plus D(m)) operations. The solution uses n plus m log m homotopy queries that are elementary; they are answerable based solely on local properties of modules, terminals, and wire connections. In addition, O(m) more complex queries are needed, and these are represented in the D(m) term. These queries must account for the total number of crossings occurring for selected test segments.",

author = "Richard Cole and Alan Siegel",

year = "1984",

doi = "10.1109/sfcs.1984.715902",

language = "English (US)",

isbn = "081860591X",

series = "Annual Symposium on Foundations of Computer Science (Proceedings)",

publisher = "IEEE",

pages = "65--73",

booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",

}

TY - GEN

T1 - RIVER ROUTING EVERY WHICH WAY, BUT LOOSE.

AU - Cole, Richard

AU - Siegel, Alan

PY - 1984

Y1 - 1984

N2 - The authors treat the DRH (detailed routing given a homotopy) problem, which deals with the placement of a set of rectangular modules within a bounding box, numbered terminals on the modules' boundaries, and a homotopy (rough routing) specification for each net. The problem is to determine whether there is a one-layer detailed routing for this configuration that conforms to the given homotopy. It is shown how to solve DRH in O(n plus m log m plus D(m)) operations. The solution uses n plus m log m homotopy queries that are elementary; they are answerable based solely on local properties of modules, terminals, and wire connections. In addition, O(m) more complex queries are needed, and these are represented in the D(m) term. These queries must account for the total number of crossings occurring for selected test segments.

AB - The authors treat the DRH (detailed routing given a homotopy) problem, which deals with the placement of a set of rectangular modules within a bounding box, numbered terminals on the modules' boundaries, and a homotopy (rough routing) specification for each net. The problem is to determine whether there is a one-layer detailed routing for this configuration that conforms to the given homotopy. It is shown how to solve DRH in O(n plus m log m plus D(m)) operations. The solution uses n plus m log m homotopy queries that are elementary; they are answerable based solely on local properties of modules, terminals, and wire connections. In addition, O(m) more complex queries are needed, and these are represented in the D(m) term. These queries must account for the total number of crossings occurring for selected test segments.

UR - http://www.scopus.com/inward/record.url?scp=0021566367&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021566367&partnerID=8YFLogxK

U2 - 10.1109/sfcs.1984.715902

DO - 10.1109/sfcs.1984.715902

M3 - Conference contribution

AN - SCOPUS:0021566367

SN - 081860591X

SN - 9780818605918

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 65

EP - 73

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - IEEE

ER -