| |
| Let $G=(V,, E)$ be a given graph with non-negative integral edgecost and delay, $Ssubseteq V$ be a terminal set and $rin S$ bethe selected root. The shallow-light Steiner tree (emph{SLST}) problemis to compute a minimum cost tree spanning the terminals of $S$,such that the delay between $r$ and every other terminal is boundedby a given delay constraint $Dinmathbb{Z}_{0}^{+}$. It is knownthat the emph{SLST} problem is NP-hard and unless $NPsubseteq DTIME(n^{loglog n})$there exists no approximation algorithm with ratio $(1,,gammalog^{2}n)$for some fixed $gamma>0$. Nevertheless,under the same assumption it admits no approximation ratio betterthan $(1,,gammalog|V|)$ for some fixed $gamma>0$ even when $D=2$.This paper first gives an exact algorithm with time complexity$O(3^{t}nD+2^{t}n^{2}D^{2}+n^{3}D^{3})$,where $n$ and $t$ are the numbers of vertices and terminals of thegiven graph respectively. This is a pseudo polynomial time parameterizedalgorithm with respect to the parameterization ``number of terminals''.Later, this algorithm is improved to a parameterized approximationalgorithm with a time complexity $O(3^{t} rac{n^{2}}{epsilon}+2^{t} rac{n^{4}}{epsilon^{2}}+ rac{n^{6}}{epsilon^{3}})$and a bifactor approximation ratio $(1+epsilon,,1)$. That is, forany small real number $epsilon>0$, the algorithm computes a Steinertree with delay and cost bounded by $(1+epsilon)D$ and the optimumcost respectively. |
|
| Keywords:Algorithm design and analysis, Shallow light Steiner tree, parameterized approximation algorithm,exact algorithm, layer graph, pseudo-polynomial time. |
|
