2006-12-01
Incremental construction of κ-dominating sets in wireless sensor networks
Publication
Publication
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 | dx.doi.org/10.1007/11945529-15 |
| Citation |
Couture, M. (Mathieu), Barbeau, M, Bose, P, & Kranakis, E. (2006). Incremental construction of κ-dominating sets in wireless sensor networks. doi:10.1007/11945529-15
|