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

DOI10.1016/j.tcs.2011.07.008zbMath1230.68216OpenAlexW1995707367MaRDI QIDQ653341

Wei Ren, Qing Zhao

Publication date: 9 January 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.07.008

zbMATH Keywords

greedy algorithmapproximation ratioconnected dominating set problemminimum connected set cover problem

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Approximability results for the converse connectedp-centre problem^†

Cites Work

• Algorithms for connected set cover problem and fault-tolerant connected set cover problem
• Approximation algorithms for connected dominating sets
• A threshold of ln n for approximating set cover

This page was built for publication: A note on `Algorithms for connected set cover problem and fault-tolerant connected set cover problem'