The Steiner tree reference article from the English Wikipedia on 24-Apr-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Steiner tree

The Steiner tree problem is a combinatorial optimization problem in mathematics. It involves a graph G with every edge having a length, with some vertices designated as terminals. A Steiner tree is a subtree of G that connects the terminals with the minimum total length (sum of all lengths of edges in the tree).

This problem might look similar to minimum spanning tree. 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 only have to connect the terminals.

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.

This is the "Steiner tree" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.