A note on 'Algorithms for connected set cover problem and fault-tolerant connected set cover problem'

作者：Ren Wei; Zhao Qing^*

来源：Theoretical Computer Science, 2011, 412(45): 6451-6454.

DOI：10.1016/j.tcs.2011.07.008

• Connected set cover
• Greedy algorithm
• Approximation ratio

A flaw in the greedy approximation algorithm proposed by Zhang et al. (2009) [1] for the minimum connected set cover problem is corrected, and a stronger result on the approximation ratio of the modified greedy algorithm is established. The results are now consistent with the existing results on the connected dominating set problem which is a special case of the minimum connected set cover problem.

• 出版日期2011-10-21