1981 | OriginalPaper | Chapter
Optimal Placement for River Routing
Authors : Charles E. Leiserson, Ron Y. Pinter
Published in: VLSI Systems and Computations
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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.