Directed Research Project Details
Distributed algorithms for the k-dominating set problem
| Author: | Dan Rao |
|---|---|
| Date: | June 10, 2005 |
| Time: | 10:00 |
| Location: | 220 Deschutes |
| Committee: | Arthur Farley (Chair) Jun Li Andrzej Proskurowski |
Abstract
The k-dominating set problem asks for a minimum subset D of nodes in a graph such that every node is either in the set or at most k hops away from a node in D. K-dominating sets have a number of applications, including center selection in a distributed network,energy-saving routing spine in a wireless network and routing with sparse routing tables.
We present distributed algorithms to find small k-dominating sets, with k fixed. We consider two different approaches and develop two sets of algorithms. Analysis and simulations show both of them run in O(k) time, and achieve reasonably small dominating sets. The first set of algorithms, which we name the Flooding, is able to compute optimally small dominating sets with the price of O(kn^2) messages, while the second set of algorithms, which we term the Flowing, finds reasonably small dominating sets with only O(kn) messages.