Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/108583
Citations  
Scopus  Web of Science®  Altmetric 

?

?

Type:  Conference paper 
Title:  On the shallowlight Steiner tree problem 
Author:  Guo, L. Liao, K. Shen, H. 
Citation:  Proceedings of the 15th Parallel and Distributed Computing, Applications and Technologies, 2015, vol.2015July, pp.5660 
Publisher:  IEEE 
Issue Date:  2015 
ISBN:  9781479983346 
Conference Name:  15th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT) (9 Dec 2014  11 Dec 2014 : Hong Kong, China) 
Statement of Responsibility:  Longkun Guo, Kewen Liao, Hong Shen 
Abstract:  Let G = (V, E) be a given graph with nonnegative integral edge cost and delay, S ⊆ V be a terminal set and +° ∈ S be the selected root. The shallowlight 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 ∈ Z+ ° . It is known that the SLST problem is NPhard and unless NP ⊆ DTIME(nlog log n) there exists no approximation algorithm with ratio (1, γ log² 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 + 2tn²D² + n³D³), 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. 
Keywords:  Shallow light Steiner tree; parameterized approximation algorithm; exact algorithm; layer graph; pseudopolynomial time 
Rights:  © 2014 IEEE 
DOI:  10.1109/PDCAT.2014.17 
Published version:  http://dx.doi.org/10.1109/pdcat.2014.17 
Appears in Collections:  Aurora harvest 8 Computer Science publications 
Files in This Item:
File  Description  Size  Format  

RA_hdl_108583.pdf Restricted Access  Restricted Access  159.45 kB  Adobe PDF  View/Open 
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.