Given a graph G, a k-dominating set of G is a subset S of its nodes with the property that every node of G is either in S or has at least k neighbors in S.We present a new incremental distributed algorithm to construct a kdominating set. The algorithm constructs a monotone family of dominating sets D1 ⊆ D2 … ⊆ Di … ⊆ Dk 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 size of an optimal i-dominating set.

Additional Metadata
Keywords Approximation algorithms, Distributed algorithms, Dominating set, Fault-tolerance, Maximal independent set, Unit disk graph
Journal Ad-Hoc and Sensor Wireless Networks
Citation
Couture, M. (Mathieu), Barbeau, M, Bose, P, & Kranakis, E. (2008). Incremental construction of k-dominating sets in wireless sensor networks. Ad-Hoc and Sensor Wireless Networks, 5(1-2), 47–67.