An Optimal Steiner Tree Algorithm for a Net Whose Terminals Lie on the Perimeter of a Rectangle

Report
Authors:Cohoon, James, Department of Computer ScienceUniversity of Virginia Richards, Dana, Department of Computer ScienceUniversity of Virginia Salowe, J, Department of Computer ScienceUniversity of Virginia
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. We present a simple, practical. linear-time exact algonthm to find the Steiner tree for points lying on the boundary of a rectangle, obviating the need for some heuristic algorithms in VLSI design. The analysis of the algorithm is based on the use of a novel tie-breaking rule that should prove useful for other Steiner tree problems. ‘r Submitted to IEEE Transactions on Computer - Aided Design of Integrated Circuits and
Note: Abstract extracted from PDF file via OCR

Rights:
All rights reserved (no additional license for public reuse)
Language:
English
Source Citation:

Cohoon, James, Dana Richards, and J Salowe. "An Optimal Steiner Tree Algorithm for a Net Whose Terminals Lie on the Perimeter of a Rectangle." University of Virginia Dept. of Computer Science Tech Report (1988).

Publisher:
University of Virginia, Department of Computer Science
Published Date:
1988