Steiner tree 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].
|[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|
Steiner tree problem. M. Hazewinkel (originator), Encyclopedia of Mathematics. URL: http://www.encyclopediaofmath.org/index.php?title=Steiner_tree_problem&oldid=15261