The Steiner tree of some subset of the vertices of a graph is a minimum-weight connected subgraph
of 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).
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 Programming64, 209-229,
1994.Chopra, S. and Rao, M. R. "The Steiner Tree Problem 2:
Properties and Classes of Facets." Mathematical Programming64,
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.
is a minimum-weight connected subgraph
of 
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).
