Contents
I. Introduction
This slot is focused on Batched Iterative 1-Steiner (BI1S) heuristic,
which solves the Rectilinear Steiner Minimum Tree (RSMT) problem efficiently.
The idea of BI1S is to find in each iteration a Steiner point which can gain
the largest wirelength saving if it is included in the pointset and a Minimum
Spanning Tree (MST) is constructed over this pointset.
This code is a new and fast implementation which updates the MST in linear time
(by updating only the nearest neighbors in four diagonal partitions) when
inserting a Steiner point.
II. Data Formats
The program computes the MST cost and Steiner tree cost under 3 kind
of modes: 1) Random pointsets, 2) Read in pointset, or 3) Automatic runs.
If 1) is chosen, the program prompts for the number of points, the
number of iterations, the grid size, and a random seed. Each pointset
of a given size is generated with a uniformed distribution over the
grid size, and the MST cost and the Steiner tree cost for the pointset
are computed and visualized in an X window.
If 2) is chosen, the program prompts for the number of
points,the grid size, and the x/y coordinate of each point. A sample
input of 4 points is as follows:
1 4
3 6
5 8
8 10
If 3) is chosen, the program prompts for the number of iterations and
a random seed. The program then automatically generates pointsets of
increasing size (from 3 to 50) over a wide range of grid sizes (from
10 to 10000).
III. Executable Utilities
-
(zipped code package)
-
-
(src code dir)
-
IV. References
-
T. Barrera, J. Griffith, G. Robins and T. Zhang, Narrowing the Gap:
Near-optimal Steiner Trees in Polynomial Time, Proc. IEEE
International ASIC Conference, Rochester, NY, September 1993, pp. 87-90.
-
T. Barrera, J. Griffith, S. A. Mckee, G. Robins and T. Zhang,
Toward a Steiner Engine: Enhanced Serial and Parallel Implementations
of the Iterated 1-Steiner Algorithm, Proc. Great Lakes Symposium on VLSI,
Kalamazoo, MI, March 1993, pp. 90-94.
-
J. Griffith, G. Robins, J. S. Salowe and T. Zhang,
Closing the Gap: Near-Optimal Steiner Trees in Polynomial Time
(.ps),
(.pdf),
IEEE Transactions on Computer-Aided Design, Vol. 13, No. 11,
November 1994, pp. 1351-1365.
-
Kahng, A. B., and Robins, G., A New Class of Iterative Steiner Tree
Heuristics With Good Performance, IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems, Vol. 11, No. 7, July 1992,
pp. 893-902.
-
Kahng, A. B., and Robins, G., A New Family of Steiner Tree Heuristics
with Good Performance: The Iterated 1-Steiner Approach, Distinguished
Paper, Proc. IEEE International Conference on Computer-Aided Design,
November 1990, pp. 428-431.
V. Contact
Dr. Gabriel Robins