TWO ALGORITHMS FOR CONNECTED r-HOP k-DOMINATING SET
Zhao Zhang, Qinghai Liu, Deying Li · Discrete Mathematics Algorithms and Applications · 2009
A vertex set D of a connected graph G is a (k, r)-connected dominating set ((k, r)-CDS) if every vertex in V(G)\D is at most r-hops away from at least k vertices in D. Finding a minimum (k, r)-CDS has wireless sensor network as its background. In this paper, we give two approximation algorithms to compute a minimum (k, r)-CDS, which improves previous works in regard of performance ratio.