A greedy approximation for minimum connected dominating sets

2004/09/18 by Lu Ruan, Hongwei Du, Xiaohua Jia +4 · 4 citations
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Mobile Ad Hoc Networks

paper · doi:10.1016/j.tcs.2004.08.013

Cited by

• On the Approximability and Hardness of the Minimum Connected Dominating Set with Routing Cost Constraint
• Connected domination in grid graphs
• Approximation Algorithm for Minimum Weight Connected m-Fold Dominating Set
• Approximations for Fault-Tolerant Total and Partial Positive Influence Domination