Steiner tree
|
|
The Steiner tree problem is a problem in combinatorial optimization. In its most general setting it is stated in a way similar to that of the minimum spanning tree problem: given a set V of points (vertices), it is required to interconnect them by a network (graph) of shortest length provided that it is allowed to add new vertices to the network. The latter possibility is the difference from the minimum spanning tree problem.
These new vertices introduced to decrease the total length of connection are known as Steiner points or Steiner vertices. It is proven that the resulting connection is a tree, known as the Steiner tree. There may be several Steiner tree for a given set of vertices.
The original problem was stated in the form that has become known as the Euclidean Steiner tree problem: Given N points in the plane, it is required to connect them by lines of minimal total length in such a way that any two points may be interconnected by line segments either directly or via other points and line segments.
It may be further generalized to the metric Steiner tree problem. Given a weighted graph <math>G (S, E, w)<math> whose vertices correspond to points in a metric space, with edge weights being the distances in the space, it is required to find a tree of minimum total length whose vertices are a superset of set S of the vertices in G.
The most general version is Steiner tree in graphs: Given a weighted graph <math>G(V, E, w)<math> and a vertices subset <math>S\subseteq V<math> find a tree of minimal weight which includes all vertices in <math>S<math>.
The metric Steiner tree problem corresponds to the Steiner tree in graphs problem where the graph has an infinite number of vertices, which are all points of the metric space.
The Steiner tree problem has applications in circuit layout or network design. Most versions of the Steiner tree problem are NP-complete, i.e., computationally hard. In fact, one of these was among Karp's original 21 NP-complete problems. Some restricted cases can be solved in polynomial time. In practice, heuristics are used.
One common approximation to the Euclidean Steiner tree problem is to compute the Euclidean minimum spanning tree.
Reference
- F.K. Hwang, D.S. Richards, P. Winter, The Steiner Tree Problem (http://www.elsevier.com/wps/find/bookdescription.librarians/523241/description#description,). Elsevier, North-Holland, 1992, ISBN 0-444-89098-X (hardbound) (Annals of Discrete Mathematics, vol. 53).de:Steinerbaumproblem