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

?

?

Full metadata record
DC Field  Value  Language 

dc.contributor.author  Guo, L.   
dc.contributor.author  Liao, K.   
dc.contributor.author  Shen, H.   
dc.date.issued  2015   
dc.identifier.citation  Proceedings of the 15th Parallel and Distributed Computing, Applications and Technologies, 2015, vol.2015July, pp.5660   
dc.identifier.isbn  9781479983346   
dc.identifier.uri  http://hdl.handle.net/2440/108583   
dc.description.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.   
dc.description.statementofresponsibility  Longkun Guo, Kewen Liao, Hong Shen   
dc.language.iso  en   
dc.publisher  IEEE   
dc.rights  © 2014 IEEE   
dc.source.uri  http://dx.doi.org/10.1109/pdcat.2014.17   
dc.subject  Shallow light Steiner tree; parameterized approximation algorithm; exact algorithm; layer graph; pseudopolynomial time   
dc.title  On the shallowlight Steiner tree problem   
dc.type  Conference paper   
dc.contributor.conference  15th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT) (9 Dec 2014  11 Dec 2014 : Hong Kong, China)   
dc.identifier.doi  10.1109/PDCAT.2014.17   
pubs.publicationstatus  Published   
dc.identifier.orcid  Shen, H. [0000000236636591] [0000000306490648]   
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.