Let G = ( V , E ) be a graph with n nodes in which each pair of nodes is joined
ID: 3864828 • Letter: L
Question
Let G = (V, E) be a graph with n nodes in which each pair of nodes is joined by an edge. There is a positive weight wij on each edge (i, j); and we will assume these weights satisfy the triangle inequality wik wij + wjk . For a subset V V, we will use G[V] to denote the subgraph (with edge weights) induced on the nodes in V.
We are given a set X V of k terminals that must be connected by edges. We say that a Steiner tree on X is a set Z so that X Z V, together with a spanning subtree T of G[Z]. The weight of the Steiner tree is the weight of the tree T.
Show that the problem of finding a minimum-weight Steiner tree on X can be solved in time O(nO(k)).
Explanation / Answer
Consider a Steiner tree represented by T in which X U Z, V|X| = k.
The X represents the terminals and Z represents the extra nodes.
Therefore, |Z| <= k.
Thus, the complexity would be O(nO(k)).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.