Generalization of Minimum Steiner Tree
Steiner trees have also been studied in the context of weighted graphs. In the general Steiner tree problem (Steiner tree in graphs), we are given an edge-weighted graph G = (V, E, w) and a subset S ⊆ V of required vertices. A Steiner tree is a tree in G that spans all vertices of S. There are two versions of the problem: in the optimization problem associated with Steiner trees, the task is to find a minimum-weight Steiner tree; in the decision problem, we are given a value k and the task is to determine whether a Steiner tree of total weight at most k exists. The decision problem was one of Karp's 21 NP-complete problems; hence the optimization problem is NP-hard.
A special case of this problem is when G is a complete graph, each vertex v ∈ V corresponds to a point in a metric space, and the edge weights w(e) for each e ∈ E correspond to distances in the space. Put otherwise, the edge weights satisfy the triangle inequality. This variant is known as the metric Steiner tree problem. Given an instance of the (non-metric) Steiner tree problem, we can transform it in polynomial time into an equivalent instance of the metric Steiner tree problem; the transformation preserves the approximation factor.
While the Euclidean version admits a PTAS, it is known that the metric Steiner tree problem is APX-complete, i.e., it is believed that arbitrarily good approximation ratios cannot in general be achieved in polynomial time. There is a polynomial-time algorithm that finds a factor 1.39 approximation of a minimum Steiner tree.
In a special case of the graph problem, the Steiner tree problem for quasi-bipartite graphs, S is required to include at least one endpoint of every edge in G.
The Steiner tree problem has also been investigated in higher dimensions and on various surfaces. Algorithms to find the Steiner minimal tree have been found on the sphere, torus, projective plane, wide and narrow cones, and others.
Another generalizations of the Steiner tree problem are the k-edge-connected Steiner network problem and the k-vertex-connected Steiner network problem, where the goal is to find a k-edge-connected graph or a k-vertex-connected graph rather than any connected graph.
Read more about this topic: Steiner Tree Problem
Famous quotes containing the words minimum, steiner and/or tree:
“After decades of unappreciated drudgery, American women just don’t do housework any more—that is, beyond the minimum that is required in order to clear a path from the bedroom to the front door so they can get off to work in the mourning.”
—Barbara Ehrenreich (20th century)
“To many men ... the miasma of peace seems more suffocating than the bracing air of war.”
—George Steiner (b. 1929)
“I have come to the conclusion that the closer people are to what may be called the front lines of government ... the easier it is to see the immediate underbrush, the individual tree trunks of the moment, and to forget the nobility the usefulness and the wide extent of the forest itself.... They forget that politics after all is only an instrument through which to achieve Government.”
—Franklin D. Roosevelt (1882–1945)