A simple improved distributed algorithm for minimum CDS in unit disk graphs
ACM Transactions on Sensor Networks (TOSN), 2006•dl.acm.org
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 …
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 …
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.
ACM Digital Library