English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs

MPS-Authors
/persons/resource/persons44464

Funke,  Stefan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45038

Meyer,  Ulrich
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Segal,  Michael
Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Funke, S., Kesselman, A., Meyer, U., & Segal, M. (2006). A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs. ACM Transactions on Sensor Networks, 2, 444-453.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2225-8
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.