Algorithm for Dynamic Programming of Kleinberg Book

372 Views Asked by At

I need help for this about answer and program of it with C.

From Kleinberg & Tardos's (2006) Algorithm Design, pp. 334–335:

29. 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 $w_{ij}$ on each edge $(i, j)$; and we will assume these weights satisfy the triangle inequality $w_{ik} ≤ w_{ij} + w_{jk}$. 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 there is function $f(·)$ and a polynomial function $p(·)$ so that the problem of finding a minimum-weight Steiner tree on $X$ can be solved in time $O(f(k)·p(n))$.