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 -