Title: A simple improved distributed algorithm for minimum CDS in unit disk graphs
Abstract: 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 connected dominating set (CDS). In this article 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. [2002]. 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.
Publication Year: 2006
Publication Date: 2006-08-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 167
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot