Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

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

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.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Funke, Stefan1, Autor           
Kesselman, Alexander, Autor
Meyer, Ulrich1, Autor           
Segal, Michael2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2Max Planck Society, ou_persistent13              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2007-04-272006
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: Expertenbegutachtung
 Identifikatoren: eDoc: 314475
Anderer: Local-ID: C1256428004B93B8-BF015BC599D1E427C12572A0006F08BD-FKesselmanMeyerS2006
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: ACM Transactions on Sensor Networks
Genre der Quelle: Zeitschrift
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 2 Artikelnummer: - Start- / Endseite: 444 - 453 Identifikator: -