The **Steiner tree problem** is a problem in combinatorial optimization. It is superficially similar to the minimum spanning tree problem: given a set *V* of points (vertices), interconnect them by a network (graph) of shortest length. The Steiner tree problem is solving this problem when adding new vertices is permitted before finding the shortest network connecting them. Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory. ...
The minimum spanning tree of a planar graph. ...
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 trees for a given set of vertices. The coniferous Sequoia, the tallest tree species on earth A tree can be defined as a large, perennial, woody plant. ...
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. In mathematics, a line segment is a part of a line that is bounded by two end points. ...
It may be further generalized to the **metric Steiner tree problem**. Given a weighted graph *G*(*S*,*E*,*w*) 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. One major problem that has plagued graph theory since its inception is the consistent lack of consistency in terminology. ...
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined. ...
The most general version is **Steiner tree in graphs**: Given a weighted graph *G*(*V*,*E*,*w*) and a vertices subset find a tree of minimal weight which includes all vertices in *S*. One major problem that has plagued graph theory since its inception is the consistent lack of consistency in terminology. ...
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. An electrical network is an interconnection of electrical elements such as resistors, inductors, capacitors, diodes, switches and transistors. ...
In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...
One of the most important results of computational complexity theory was Stephen Cooks 1971 paper that demonstrated the first NP-complete problem, the boolean satisfiability problem. ...
In mathematics, a polynomial is an expression in which constants and powers of variables are combined using (only) addition, subtraction, and multiplication. ...
For heuristics in computer science, see heuristic (computer science) Heuristic is the art and science of discovery and invention. ...
One common approximation to the Euclidean Steiner tree problem is to compute the Euclidean minimum spanning tree. An EMST computed and drawn by Leda, a C++ commercial algorithm library; see the External Links section The Euclidean minimum spanning tree or EMST is a minimum spanning tree of a set of points in the plane, where the weight of the edge between each pair of points is the...
## 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). |