## Abstract

Let G = (V, E) be a given graph with nonnegative integral edge cost and delay, S V be a terminal set and r ∈ S be the selected root. The shallow-light Steiner tree (SLST) problem is to compute a minimum cost tree spanning the terminals of S, such that the delay between r and every other terminal is bounded by a given delay constraint D ∈ ℤ^{+}_{0} . It is known that the SLST problem is NP-hard and unless NP ⊆ DTIME(n^{log log n}) there exists no approximation algorithm with ratio (1, γ log^{2} n) for some fixed γ > 0 [12]. Nevertheless, under the same assumption it admits no approximation ratio better than (1, γ log |V|) for some fixed γ > 0 even when D = 2 [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 the given graph respectively. This is a pseudo polynomial time parameterized algorithm with respect to the parameterization "number of terminals". Later, this algorithm is improved to a parameterized approximation algorithm with a time complexity O(3^{t} n^{2}/∈ + 2^{t} n^{4}/∈^{2}+n^{6}/∈^{3}) and a bifactor approximation ratio (1 + ∈, 1). That is, for any small real number ∈ > 0, the algorithm computes a Steiner tree with delay and cost bounded by (1 + ∈)D and the optimum cost respectively.

Original language | English |
---|---|

Title of host publication | Proceedings - 15th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2014 |

Publisher | IEEE Computer Society |

Pages | 56-60 |

Number of pages | 5 |

Volume | 2015-July |

ISBN (Electronic) | 9781479983346 |

DOIs | |

Publication status | Published - 1 Jan 2015 |

Externally published | Yes |

Event | 15th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2014 - Hong Kong, China Duration: 9 Dec 2014 → 11 Dec 2014 |

### Conference

Conference | 15th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2014 |
---|---|

Country | China |

City | Hong Kong |

Period | 9/12/14 → 11/12/14 |