• DocumentCode
    2663882
  • Title

    A neighborhood improvement algorithm for rectilinear Steiner trees

  • Author

    Hasan, N. ; Vijayan, G. ; Wong, C.K.

  • Author_Institution
    Dept. of Comput. Sci., Illinois Univ., Urbana, IL, USA
  • fYear
    1990
  • fDate
    1-3 May 1990
  • Firstpage
    2869
  • Abstract
    A heuristic algorithm for constructing a rectilinear Steiner tree (RST) from a rectilinear minimum-spanning tree of a given point set is described. The heuristic algorithm is based on replacing neighborhood structures of an independent set of rectilinear minimum-spanning tree points by their optimal RSTs. The time complexity of each iteration of the algorithm is O(n log n), where n is the cardinality of the input point set
  • Keywords
    computational complexity; network topology; trees (mathematics); heuristic algorithm; neighborhood improvement algorithm; rectilinear Steiner trees; rectilinear minimum-spanning; time complexity; Computer science; Cost function; Heuristic algorithms; Iterative algorithms; LAN interconnection; Tree graphs;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Circuits and Systems, 1990., IEEE International Symposium on
  • Conference_Location
    New Orleans, LA
  • Type

    conf

  • DOI
    10.1109/ISCAS.1990.112609
  • Filename
    112609
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2663882