An optimal Steiner tree algorithm for a net whose terminals lie on the perimeter of a rectangle
- 1 April 1990
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 9 (4) , 398-407
- https://doi.org/10.1109/43.45871
Abstract
Given a set of input points, the rectilinear Steiner tree problem is to find a minimal-length tree consisting of vertical and horizontal line segments that connects the input points, where it is possible to add new points to minimize the length of the tree. The restricted Steiner tree problem in which all the input points lie on the boundary of a rectangle frequently occurs in VLSI physical design. Since the fastest published algorithm is cubic in the size of the point set, VLSI designers have been forced to use heuristic approximations to the length of the Steiner tree for this problem. A simple, practical, linear-time exact algorithm for finding the Steiner tree for points lying on the boundary of a rectangle which obviates the need for some heuristic algorithms in VLSI design is presented. The analysis of the algorithm is based on the use of a tie-breaking rule that should prove useful for other Steiner tree problemsKeywords
This publication has 4 references indexed in Scilit:
- A Procedure for Placement of Standard-Cell VLSI CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1985
- The Rectilinear Steiner Tree Problem is $NP$-CompleteSIAM Journal on Applied Mathematics, 1977
- Rectilinear steiner trees: Efficient special-case algorithmsNetworks, 1977
- On Steiner Minimal Trees with Rectilinear DistanceSIAM Journal on Applied Mathematics, 1976