RIVER ROUTING EVERY WHICH WAY, BUT LOOSE.

Research output: Chapter in Book/Report/Conference proceedingConference 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 languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherIEEE
Pages65-73
Number of pages9
ISBN (Print)081860591X, 9780818605918
DOIs
StatePublished - 1984

Publication series

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

ASJC Scopus subject areas

  • Hardware and Architecture

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

Cite this