TOPICS
Search

Steiner Tree


SteinerTree

The Steiner tree of some subset of the vertices of a graph G is a minimum-weight connected subgraph of G that includes all the vertices. It is always a tree. Steiner trees have practical applications, for example, in the determination of the shortest total length of wires needed to join some number of points (Hoffman 1998, pp. 164-165).

The determination of a Steiner tree is NP-complete and hard even to approximate. There is 1.55-approximate algorithm due to Robins and Zelikovski (2000), but approximation within 95/94 is known to be NP-hard (Chlebik and Chlebikova 2002).


See also

Plateau's Problem, Tree

Explore with Wolfram|Alpha

References

Chlebik, M. and J.Chlebikova, J. "Approximation Hardness of the Steiner Tree Problem on Graphs." Proc. 8th Scandinavian Workshop on Algorithm Theory (SWAT). Springer-Verlag, pp. 170-179, 2002.Chopra, S. and Rao, M. R. "The Steiner Tree Problem 1: Formulations, Compositions, and Extension of Facets." Mathematical Programming 64, 209-229, 1994.Chopra, S. and Rao, M. R. "The Steiner Tree Problem 2: Properties and Classes of Facets." Mathematical Programming 64, 231-246, 1994.Chung, F. R. K.; Gardner, M.; and Graham, R. L. "Steiner Trees on a Checkerboard." Math. Mag. 62, 83-96, 1989.Cieslik, D. Steiner Minimal Trees. Amsterdam: Kluwer, 1998.Du, D.-Z.; Smith, J. M.; and Rubinstein, J. H. Advances in Steiner Trees. Dordrecht, Netherlands: Kluwer, 2000.Ganley, J. "The Steiner Tree Page." http://ganley.org/steiner/.Hoffman, P. The Man Who Loved Only Numbers: The Story of Paul Erdős and the Search for Mathematical Truth. New York: Hyperion, 1998.Hwang, F.; Richards, D.; and Winter, P. The Steiner Tree Problem. Amsterdam, Netherlands: North-Holland, 1992.Ivanov, A. O. and Tuzhilin, A. A. Minimal Networks: The Steiner Problem and Its Generalizations. Boca Raton, FL: CRC Press, 1994.Robins, G. and Zelikovski, A. "Improved Steiner Tree Approximation in Graphs." In Proc. 11th ACM-SIAM Symposium on Discrete Algorithms. pp. 770-779, 2000.Skiena, S. S. "Steiner Tree." §8.5.10 in The Algorithm Design Manual. New York: Springer-Verlag, pp. 339-342, 1997.

Referenced on Wolfram|Alpha

Steiner Tree

Cite this as:

Weisstein, Eric W. "Steiner Tree." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SteinerTree.html

Subject classifications