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

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.)

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.

for k = 4, . . . , n do

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

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

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

Remove the edge (a; b).

Add the edges (t

_{k}; s), (a; s), (b; s).Run the local optimization routine.

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

Set the current tree to old tree.

Set the current tree to best tree.

Set the final tree to the current tree.

[1] B. Aronov, M. Bern, and D. Eppstein, "On the number of minimal 1-Steiner trees"

[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.

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

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

[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.

[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.

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

**Steiner Tree Problem Applet**

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