Namespaces
Variants
Actions

Steiner tree problem

From Encyclopedia of Mathematics
Revision as of 17:11, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Steiner problem

Given a set 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 . The Steiner minimum tree may well have some vertices that are not in . 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 -hard.

A Steiner minimum tree in the Euclidean plane has the following properties:

1) all leaves are regular points;

2) every two edges meet at an angle of at least ;

3) every Steiner point has degree at least three.

A tree satisfying these three conditions and connecting all points of (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 ; 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://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