A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs
Stefan Funke, Alexander Kesselman, Ulrich Meyer, Michael Segal
Several routing schemes in ad hoc networks
first establish a virtual backbone and then route messages
via backbone nodes. One common way of constructing
such a backbone is based on the construction of a minimum connected dominating
set (CDS).
In this paper we present a very simple distributed
algorithm for computing a small CDS.
Our algorithm has an
approximation factor of at most $6.91$, improving upon
the previous best known approximation factor of $8$ due to
Wan et al. [INFOCOM'02].
The improvement relies on a refined analysis
of the relationship between
the size of a maximal independent set and
a minimum CDS in a unit disk graph. This subresult also implies
improved approximation factors for many existing algorithms.
PDF