pith. sign in

arxiv: 1104.0733 · v1 · pith:W5NH5SIHnew · submitted 2011-04-05 · 💻 cs.DS

A Note on: `Algorithms for Connected Set Cover Problem and Fault-Tolerant Connected Set Cover Problem'

classification 💻 cs.DS
keywords connectedproblemcoveralgorithmapproximationgreedyminimumresults
0
0 comments X
read the original abstract

A flaw in the greedy approximation algorithm proposed by Zhang et al. for 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 connected dominating set problem which is a special case of the minimum connected set cover problem.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.