An Efficient Distributed Algorithm for Constructing Small Dominating Sets

The dominating set problem asks for a subset D of nodes in a given
graph, such that every node is either in D or adjacent to a node in 
D. Solution to dominating sets is useful in a number of distributed
network applications, where the goal is to select a subset of nodes
that act as centers for a certain service, and every node in the
network is close to some center in this network.  A variant of
dominating sets, k-dominating sets can be used to locate servers or
copies of a distributed directory such that every node is within a
distance k of some server or directory copy.  In ad hoc network,
dominating sets have been proposed to store routing information.

  Finding a dominating set of minimum size is NP-complete, and the best
known approximation is logarithmic and is provided by the same
centralized greedy approach for the set cover problem.  A number of
parallel set cover algorithms have been proposed to achieve
logarithmic approximation, but they employ certain global
synchronizations which makes it nontrivial to transform them into fast
distributed implementation.  A distributed version of the greedy
approach has also been proposed to achieve the same approximation
ratio as in the centralized greedy, but linear time is required when
it is applied to certain networks.  We propose in this paper a simple
 distributed algorithm, Local Randomized Greedy algorithm, that terminates
in logarithmic time, and achieves a logarithmic approximation ratio with
high probability for arbitrary networks. Besides the basic dominating set,
we consider as well common generalizations, such as the weighted case and
the multiple coverage dominating set, and give similar results as in our
main algorithm.