Given a graph G, a κ-dominating set of G is a subset S of its vertices with the property that every vertex of G is either in S or has at least κ neighbors in S. We present a new incremental distributed algorithm to construct a κ-dominating set. The algorithm constructs a monotone family of dominating sets D1 ⊆ D2. ⊆ Di. ⊆ Dκ such that each Di is an i-dominating set. For unit disk graphs, the size of each of the resulting i-dominating sets is at most six times the optimal.

Additional Metadata
Keywords Approximation algorithms, Distributed algorithms, Dominating set, Fault-tolerance, Maximal independent set, Unit disk graph
Persistent URL
Couture, M. (Mathieu), Barbeau, M, Bose, P, & Kranakis, E. (2006). Incremental construction of κ-dominating sets in wireless sensor networks. doi:10.1007/11945529-15