# Steiner tree problem

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].

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