A simple improved distributed algorithm for minimum CDS in unit disk graphs

Several routing schemes in ad hoc networks first establish a virtual backbone and then route messages via back-bone 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 algorithm.