Authentication email has already been sent, please check your email box: and activate it as soon as possible.
You can login to My Profile and manage your email alerts.
If you haven’t received the email, please:
|
|
There are 1 papers published in subject: > since this site started. |
Results per page: |
Select Subject |
Select/Unselect all | For Selected Papers |
Saved Papers
Please enter a name for this paper to be shown in your personalized Saved Papers list
|
1. Parameterized Approximation Algorithms for the Shallow-Light Steiner Tree Problem | |||
GUO Longkun, LIAO Kewen, SHEN Hong | |||
Computer Science and Technology 02 June 2015 | |||
Show/Hide Abstract | Cite this paper︱Full-text: PDF (0 B) | |||
Abstract: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. | |||
TO cite this article:GUO Longkun, LIAO Kewen, SHEN Hong . Parameterized Approximation Algorithms for the Shallow-Light Steiner Tree Problem[OL].[ 2 June 2015] http://en.paper.edu.cn/en_releasepaper/content/4640692 |
Select/Unselect all | For Selected Papers |
Saved Papers
Please enter a name for this paper to be shown in your personalized Saved Papers list
|
Results per page: |
About Sciencepaper Online | Privacy Policy | Terms & Conditions | Contact Us
© 2003-2012 Sciencepaper Online. unless otherwise stated