Steiner Tree Problem's Heuristic
with Minimum Spanning Tree Problem

 

The Steiner tree problem is a minimum interconnection problem. The most basic version is in a graph theory that can be state as follows:

 

Given a weighted graph in which a subset of vertices are identified as terminals, find a minimum-weight connected subgraph that includes all the terminals.
 

If the edge weights are all positive, then the resulting subgraph is obviously a tree.
 

The problem can also be applied in the geometric realm; the two most common variants are the Euclidean Steiner tree and rectilinear Steiner tree problems. Here, the input is a set of points in space that are the terminals, and the objective is to compute a tree of minimum length (in the appropriate metric) that connects all the terminals. In addition to the Euclidean and rectilinear metrics, the hexagonal and octagonal metrics have been considered. More recently, researchers have considered Steiner trees that minimize certain estimates of electrical delay and other objectives.

 

The Incremental Optimization Algorithm

  1. Order the fixed points by the distance from their mean, the first being closest to it. (This ordering step greatly reduces the dependency of the final tree on the initial ordering of the points, although there can still be ties.)
     

  2. Insert a Steiner point between the first three fixed points, connect it to each, and locally optimize to obtain the Steiner tree for those three points. Call it the current tree.
     

  3. for k = 4, . . . , n do

    1. Save the current tree as old tree and set best tree to an artificial tree with length ∞.

    2. for each edge (a; b) of the current tree do

      1. Place a Steiner point s on the edge (a; b).

      2. Remove the edge (a; b).

      3. Add the edges (tk; s), (a; s), (b; s).

      4. Run the local optimization routine.

      5. If the resulting tree is shorter than best tree, then set best tree to this new tree.

      6. Set the current tree to old tree.

    3. Set the current tree to best tree.
       

  4. Set the final tree to the current tree.

 

Reference

 

[1]   B. Aronov, M. Bern, and D. Eppstein, "On the number of minimal 1-Steiner trees". Discrete and Computational Geometry", pages 29-34, 1994.

[2]   P. Berman and V. Ramaiyer, "Improved approximations for the Steiner tree problem", In Proceedings of the Third Symposium on Discrete Algorithms, pages 325-334, 1992.

[3]   M. W. Bern, "Two probabilistic results on rectilinear Steiner trees", Algorithmica, 3:191-204, 1988.

[4]   M. Bern, "Faster exact algorithms for Steiner trees in planar networks", Networks, 20:109-120, 1990.

[5]   P. Berman and V. Ramaiyer, "Improved approximations for the Steiner tree problem", Journal of Algorithms, 17:381-408, 1994.

[6]   R. S. Booth, "Analytic formulas for full Steiner trees", Discrete and Computational Geometry, 6:69-82, 1991.

[7]   W. M. Boyce, "An improved program for the full Steiner tree problem", ACM Transactions on Mathematical Software, 3:359-385, 1977.

[8]   J.-D. Cho, "A min-cost flow base min-cost rectilinear Steiner distance-preserving tree construction",  In Proceedings of the International Symposium on Physical Design, pages 82-87, 1997.

[9]   F. R. K. Chung and F. K. Hwang, "A lower bound for the Steiner tree problem",  SIAM Journal on Applied Mathematics, 34:27-36, 1978.

[10] Cloutier and I. Bennour, "Topological characterization of Hwang's optimal Steiner trees", In Proceedings of the Canadian Conference on Computational Geometry, pages 157-162, 1993.

[11] E. J. Cockayne and D. E. Hewgill, "Improved computation of plane Steiner minimal trees", Algorithmica, 7:219-229, 1992.

[12] E. J. Cockayne, "On the Steiner problem", Canadian Mathematical Bulletin, 10:431-450, 1967.

 

 

Steiner Tree Problem Applet


 

 

 

 

Minimum Spanning Tree Problem Applet

Here is the minimum spanning tree applet in case you would like to campare Steiner tree problem with MST problem.