Namespaces
Variants
Actions

Steiner tree problem

From Encyclopedia of Mathematics
Jump to: navigation, search

Steiner problem

Given a set $P$ of points in a metric space, the problem is to find a shortest network connecting all the points in the set. An optimal solution to this problem is called a Steiner minimum tree for $P$. The Steiner minimum tree may well have some vertices that are not in $P$. Such vertices are called Steiner nodes or Steiner points, and the other points are called regular points. These points should not be confused with the Steiner point of a convex body.

For subsets of networks, the Steiner tree problem is a special network optimization problem. The Steiner tree problem is $\mathcal{NP}$-hard.

A Steiner minimum tree in the Euclidean plane $E^2$ has the following properties:

1) all leaves are regular points;

2) every two edges meet at an angle of at least $120^\circ$;

3) every Steiner point has degree at least three.

A tree satisfying these three conditions and connecting all points of $P\subset E^2$ (as regular points) is called a Steiner tree.

The Steiner ratio is the ratio between the length of a minimum Steiner tree and a shortest spanning tree (see Tree). The Gilbert–Pollak conjecture [a3] says that the Steiner ratio of the Euclidean plane is $\sqrt3/2$; it was proved in [a2].

References

[a1] Ding-Zhu Du, "Minimax and its applications" R. Horst (ed.) P.M. Pardalos (ed.) , Handbook of Global Optimization , Kluwer Acad. Publ. (1995) pp. 339–368
[a2] Ding-Zhu Du, F.K. Hwang, "A proof of the Gilbert–Pollak conjecture" Algorithmica , 7 (1992) pp. 121–135
[a3] E.N. Gilbert, H.O. Pollak, "Steiner minimal trees" SIAM J. Appl. Math. , 16 (1968) pp. 1–29
How to Cite This Entry:
Steiner tree problem. Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Steiner_tree_problem&oldid=34103
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article