A note on ‘Algorithms for connected set cover problem and fault-tolerant connected set cover problem’
Copyright policy )A note on ‘Algorithms for connected set cover problem and fault-tolerant connected set cover problem’
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.
6 pages, 1 figure, submitted to Theoretical Computer Science
- University of California, Davis United States
- University of California United States
- University of California United States
- University of California, San Francisco United States
- Dept. of Electrical and Computer Engineering United States
FOS: Computer and information sciences, Connected set cover, connected dominating set problem, Approximation algorithms, Approximation ratio, Theoretical Computer Science, greedy algorithm, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), minimum connected set cover problem, Graph algorithms (graph-theoretic aspects), Greedy algorithm, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), approximation ratio, Computer Science(all)
FOS: Computer and information sciences, Connected set cover, connected dominating set problem, Approximation algorithms, Approximation ratio, Theoretical Computer Science, greedy algorithm, Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), minimum connected set cover problem, Graph algorithms (graph-theoretic aspects), Greedy algorithm, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), approximation ratio, Computer Science(all)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).8 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!