Paper Info
Title
A New Approach to the Rectilinear Steiner Tree Problem
Abstract
We discuss a new approach to constructing the rectilinear Steiner tree (RST) of a given set of points in the plane, starting from a minimum spanning tree (MST). The main idea in our approach is to determine L-shaped layouts for the edges of the MST, so as to maximize the overlaps between the layouts, thus minimizing the cost (i.e., wire length) of the resulting RST. We describe a linear time algorithm for constructing a RST from a a MST, such that the RST is optimal under the restriction that the layout of each edge of the MST is an L-shape. The RST's produced by this algorithm have 8-33% lower cost than the MST, with the average cost improvement, over a large number of random point sets, being about 9%. The running time of the algorithm on an IBM 3090 processor is under 0.01 seconds for point sets with cardinality 10. We also discuss a property of RST's called stability under rerouting, and show how to stabilize the RST's derived from our approach. Stability is a desirable property in VLSI global routing applications.
Year
DOI
Venue
1989
10.1109/DAC.1989.203388
DAC
Keywords
Field
DocType
l-shaped layout,random point set,lower cost,linear time algorithm,point set,rectilinear steiner tree problem,average cost improvement,desirable property,rectilinear steiner tree,new approach,vlsi global routing application,very large scale integration,steiner tree problem,routing,minimum spanning tree,stability,steiner tree
Permission,Discrete mathematics,Computer science,Cardinality,Average cost,Rectilinear Steiner tree,IBM 3090,Time complexity,Very-large-scale integration,Minimum spanning tree
Conference
ISSN
ISBN
Citations 
0738-100X
0-89791-310-8
20
PageRank 
References 
Authors
1.91
4
3
Name
Order
Citations
PageRank
Jan-Ming Ho1950106.64
G. Vijayan218125.99
C. K. Wong31459513.44