Approximation Algorithms for Steiner Connected Dominating Set

Steiner connected dominating set (SCDS) is a generalization of the famous connected dominating set problem, where only a specified set of required vertices has to be dominated by a connected dominating set, and known to be NP-hard. This paper firstly modifies the SCDS algorithm of Guha and Khuller a...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer science and technology 2005-09, Vol.20 (5), p.713-716
Main Authors: Wu, Ya-Feng, Xu, Yin-Long, Chen, Guo-Liang
Format: Article
Language:English
Subjects:
Algorithms
Apexes
Approximation
Graph theory
Graphs
Greedy algorithms
Harmonic functions
Mathematical analysis
Mathematical models
Optimization
Studies
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Steiner connected dominating set (SCDS) is a generalization of the famous connected dominating set problem, where only a specified set of required vertices has to be dominated by a connected dominating set, and known to be NP-hard. This paper firstly modifies the SCDS algorithm of Guha and Khuller and achieves a worst case approximation ratio of (2+1/(m−1))H(min (D, k))+O(1), which outperforms the previous best result (c+1)H(min (D, k))+O(1) in the case of mge 1+1/(c−1), where c is the best approximation ratio for Steiner tree, D is the maximum degree of the graph, k is the cardinality of the set of required vertices, m is an optional integer satisfying 0≤ m ≤ min (D, k) and H is the harmonic function. This paper also proposes another approximation algorithm which is based on a greedy approach. The second algorithm can establish a worst case approximation ratio of 2ln (min (D, k))+O(1), which can also be improved to 2ln k if the optimal solution is greater than .
ISSN:1000-9000
1860-4749
DOI:10.1007/s11390-005-0713-x