"Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc
Networks"

Khaled M. Alzoubi (Illinois Institute of Technology)

Connected dominating set (CDS) has been proposed as virtual backbone or a
spine for wireless ad hoc networks. The topology of wireless ad hoc networks
is modelled as a unit-disk graph. However, it is NP-hard to find a minimum
connected dominating set (MCDS) in general graphs, and it remains NP-hard
for the unit-disk graph. Approximation algorithms for MCDS have been
proposed in the literature. All of these algorithms suffer from a linear or
logarithmic approximation ratio, and from high time complexity and/or
message complexity.

In this paper, we first establish a lower bound on the message complexity of
any distributed algorithm for nontrivial CDS in the unit-disk graph. Then,
we introduce an algorithm with performance ratio of 8, O(n log n) messages,
and O(n) time. This is the first distributed algorithm with constant
performance ratio.