• DocumentCode
    2790258
  • Title

    A fast approximation to the rectilinear Steiner tree problem

  • Author

    Katsadas, Evagelos E. ; Kinnen, Edwin

  • Author_Institution
    Dept. of Electr. Eng., Rochester Univ., NY, USA
  • fYear
    1990
  • fDate
    12-14 Aug 1990
  • Firstpage
    188
  • Abstract
    A new algorithm is presented for the construction of a suboptimal rectilinear Steiner tree (RST). The algorithm utilizes the notion of possible Steiner points to obtain a suboptimal solution of the problem in O(n2) time. An extension of the algorithm allows the creation of RSTs that are stable under rerouting. Implementation of the algorithm on a number of randomly generated examples indicates fast CPU execution time and good quality of solutions when compared to other known algorithms
  • Keywords
    circuit layout CAD; network topology; trees (mathematics); CPU execution time; fast approximation; rectilinear Steiner tree problem; rerouting; suboptimal solution; Approximation algorithms; Costs; Heuristic algorithms; Random number generation; Routing; Stability; Very large scale integration;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Circuits and Systems, 1990., Proceedings of the 33rd Midwest Symposium on
  • Conference_Location
    Calgary, Alta.
  • Print_ISBN
    0-7803-0081-5
  • Type

    conf

  • DOI
    10.1109/MWSCAS.1990.140683
  • Filename
    140683
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2790258