Paper Info
Title
Constructing the optimal rectilinear Steiner tree derivable from a minimum spanning tree
Abstract
A polynomial time algorithm is given for constructing the minimum cost rectilinear Steiner tree (RST) that is derivable from a minimum spanning tree (MST) of a given point set, such that the MST edges have staircase layouts in the RST. RSTs produced by the algorithm have a property called stability, which enables the rerouting of any subset of the RST edges, while maintaining the cost of the RST, and not causing overlaps with each other or with the other RST edges.<>
Year
DOI
Venue
1989
10.1109/ICCAD.1989.76893
ICCAD
Keywords
Field
DocType
staircase layouts,trees (mathematics),minimum cost rectilinear steiner tree,optimal rectilinear steiner tree,circuit layout cad,polynomial time algorithm,minimum spanning tree,computational complexity,point set,subset,edges,stability,rerouting,steiner tree
Discrete mathematics,Combinatorics,k-minimum spanning tree,Prim's algorithm,Steiner tree problem,Euclidean minimum spanning tree,Rectilinear Steiner tree,Spanning tree,Kruskal's algorithm,Mathematics,Minimum spanning tree
Conference
Citations 
PageRank 
References 
5
1.07
5
Authors
3
Name
Order
Citations
PageRank
Jan-Ming Ho1950106.64
G. Vijayan218125.99
C. K. Wong31459513.44