Title :
Routing in a rectangle with k-ary overlap
Author :
Hamkins, Jon ; Brown, Donna J.
Author_Institution :
Beckman Inst., Illinois Univ., Urbana, IL, USA
Abstract :
A layout for the k-ary overlap rectangle routing problem (k-RRP) is a set of paths connecting pairs of terminals on the boundary such that each edge hosts at most k distinct nets. The authors give necessary and sufficient conditions for the existence of such a layout, and present an algorithm that constructs a layout, if one exists, in time O(kN), where N is the number of gridpoints in the rectangle. Extensions to more general problems are also discussed
Keywords :
VLSI; circuit layout CAD; k-ary overlap; necessary and sufficient conditions; rectangle routing problem; Contracts; Joining processes; Nonhomogeneous media; Routing; Sufficient conditions; Very large scale integration; Wires; Wiring;
Conference_Titel :
VLSI, 1992., Proceedings of the Second Great Lakes Symposium on
Conference_Location :
Kalamazoo, MI
Print_ISBN :
0-8186-2610-0
DOI :
10.1109/GLSV.1992.218352
