1981 | OriginalPaper | Buchkapitel
Optimal Placement for River Routing
verfasst von : Charles E. Leiserson, Ron Y. Pinter
Erschienen in: VLSI Systems and Computations
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
River routing is the problem of connecting a set of terminals a1,…,an on a line to another set b1,…,bn in order across a rectangular channel. When the terminals are located on modules, the modules must be placed relative to one another before routing. This placement problem arises frequently in design systems like bristle-blocks where stretch lines through a module can effectively break it into several chunks, each of which must be placed separately. This paper gives concise necessary and sufficient conditions for wirability which are applied to reduce the optimal placement problem to the graph-theoretic single-source-longest-paths problem. By exploiting the special structure of graphs that arise from the placement problem for rectilinear wiring, an optimal solution may be determined in linear time.