Approximation Algorithms for Steiner Connected Dominating Set
Yafeng, Wu, Yin-long, Xu, Guoliang, Chen · Acta Scientiarum Naturalium Universitatis Sunyatseni · 2005
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 NPhard. 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(△, k)) + O(1), which outperforms the previous best result (c + 1)H(min(△, k)) + O(1) in the case of m ≥ 1 + 1/(c - 1), where c is the best approximation ratio for Steiner tree, △ 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(△, 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(△, k)) + O(1), which can also be improved to 2 ln k if the optimal solution is greater than c.e2c+1/2(c+1) .