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 shoot a man because one disagrees with his interpretation of Darwin or Hegel is a sinister tribute to the supremacy of ideas in human affairs—but a tribute nevertheless.”
—George Steiner (b. 1929)
“Some say that happiness is not good for mortals, & they ought to be answered that sorrow is not fit for immortals & is utterly useless to any one; a blight never does good to a tree, & if a blight kill not a tree but it still bear fruit, let none say that the fruit was in consequence of the blight.”
—William Blake (1757–1827)