A simple improved distributed algorithm for minimum CDS in unit disk graphs
Authors:
Open Access
- 1 August 2006
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Sensor Networks
- Vol. 2 (3) , 444-453
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.Keywords
This publication has 9 references indexed in Scilit:
- Weakly-connected dominating sets and sparse spanners in wireless ad hoc networks2004
- Distributed Construction of Connected Dominating Set in Wireless Ad Hoc NetworksMobile Networks and Applications, 2004
- Connected dominating set and its induced position-less sparse spanner for mobile ad hoc networks2004
- A polynomial‐time approximation scheme for the minimum‐connected dominating set in ad hoc wireless networksNetworks, 2003
- Simple heuristics for unit disk graphsNetworks, 1995
- Removing randomness in parallel computation without a processor penaltyJournal of Computer and System Sciences, 1993
- Unit disk graphsDiscrete Mathematics, 1990
- A Simple Parallel Algorithm for the Maximal Independent Set ProblemSIAM Journal on Computing, 1986
- ber die dichteste KugellagerungMathematische Zeitschrift, 1942