Steiner tree

The Steiner tree problem is a combinatorial optimization problem in mathematics. It involves a graph G with a set of vertices. A Steiner tree is a tree of minimum total length whose vertices are a superset of the vertices in G. Those vertices that are not in G are called Steiner points.

This problem might look similar to minimum spanning tree (MST). The main difference is that, in the minimum spanning tree problem, we are looking for a tree that connects all vertices of G. In Steiner tree problem, we add extra vertices to reduce the overall length.

The Steiner tree problem has applications in circuit layout or network design . The Steiner tree problem is NP-complete. Some restricted cases can be solved in polynomial time. In practice, heuristics are used.

One common approximation to the Steiner tree problem is to compute the Euclidean minimum spanning tree.

Reference

• F.K. Hwang, D.S. Richards, P. Winter, The Steiner Tree Problem. Elsevier, North-Holland , 1992, ISBN 0-444-89098-X (hardbound) (Annals of Discrete Mathematics , vol. 53).