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
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;
Conference_Titel :
Circuits and Systems, 1990., IEEE International Symposium on
Conference_Location :
New Orleans, LA
DOI :
10.1109/ISCAS.1990.112609
