TY - GEN

T1 - On the Shallow-Light Steiner Tree Problem

AU - Guo, Longkun

AU - Liao, Kewen

AU - Shen, Hong

N1 - Publisher Copyright:
© 2014 IEEE.

PY - 2015/7/31

Y1 - 2015/7/31

N2 - 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.

AB - 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.

KW - Pseudo-polynomial time

KW - Shallow light Steiner tree

KW - exact algorithm

KW - layer graph

KW - parameterized approximation algorithm

UR - http://www.scopus.com/inward/record.url?scp=84946143842&partnerID=8YFLogxK

U2 - 10.1109/PDCAT.2014.17

DO - 10.1109/PDCAT.2014.17

M3 - Conference contribution

AN - SCOPUS:84946143842

T3 - Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings

SP - 56

EP - 60

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

PB - IEEE Computer Society

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

Y2 - 9 December 2014 through 11 December 2014

ER -