On the shallow-light Steiner tree problem
| dc.contributor.author | Guo, L. | |
| dc.contributor.author | Liao, K. | |
| dc.contributor.author | Shen, H. | |
| 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.date.issued | 2015 | |
| 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 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 ∈ Z+ ° . 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, γ 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.identifier.citation | Proceedings of the 15th Parallel and Distributed Computing, Applications and Technologies, 2015, vol.2015-July, pp.56-60 | |
| dc.identifier.doi | 10.1109/PDCAT.2014.17 | |
| dc.identifier.isbn | 9781479983346 | |
| dc.identifier.orcid | Shen, H. [0000-0002-3663-6591] [0000-0003-0649-0648] | |
| dc.identifier.uri | http://hdl.handle.net/2440/108583 | |
| dc.language.iso | en | |
| dc.publisher | IEEE | |
| dc.rights | © 2014 IEEE | |
| dc.source.uri | https://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 shallow-light Steiner tree problem | |
| dc.type | Conference paper | |
| pubs.publication-status | Published |
Files
Original bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- RA_hdl_108583.pdf
- Size:
- 159.45 KB
- Format:
- Adobe Portable Document Format
- Description:
- Restricted Access