• DocumentCode
    3164095
  • Title

    Routing in a rectangle with k-ary overlap

  • Author

    Hamkins, Jon ; Brown, Donna J.

  • Author_Institution
    Beckman Inst., Illinois Univ., Urbana, IL, USA
  • fYear
    1992
  • fDate
    28-29 Feb 1992
  • Firstpage
    144
  • Lastpage
    151
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    VLSI, 1992., Proceedings of the Second Great Lakes Symposium on
  • Conference_Location
    Kalamazoo, MI
  • Print_ISBN
    0-8186-2610-0
  • Type

    conf

  • DOI
    10.1109/GLSV.1992.218352
  • Filename
    218352
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3164095