On the Shallow-Light Steiner Tree Problem

Longkun Guo, Kewen Liao, Hong Shen

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

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(nlog log n) there exists no approximation algorithm with ratio (1, γ log2 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(3tnD + 2tn2D2 + n3D3), 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(3t n2/∈ + 2t n4/∈2+n6/∈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 languageEnglish
Title of host publicationProceedings - 15th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2014
PublisherIEEE Computer Society
Pages56-60
Number of pages5
Volume2015-July
ISBN (Electronic)9781479983346
DOIs
Publication statusPublished - 1 Jan 2015
Externally publishedYes
Event15th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2014 - Hong Kong, China
Duration: 9 Dec 201411 Dec 2014

Conference

Conference15th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2014
CountryChina
CityHong Kong
Period9/12/1411/12/14

    Fingerprint

Cite this

Guo, L., Liao, K., & Shen, H. (2015). On the Shallow-Light Steiner Tree Problem. In Proceedings - 15th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2014 (Vol. 2015-July, pp. 56-60). [7174766] IEEE Computer Society. https://doi.org/10.1109/PDCAT.2014.17