Journal Article
@Article
Artikel in Fachzeitschrift

Show entries of:

this year (2022) | last year (2021) | two years ago (2020) | Notes URL

Action:

login to update
Options:








Author, Editor(s)
Author(s):
Funke, Stefan
Kesselman, Alexander
Meyer, Ulrich
Segal, Michael		dblp
dblp
dblp
dblp
Not MPG Author(s):
Funke, Stefan
Segal, Michael

BibTeX cite key*:

FKesselmanMeyerS2006

Title

Title*:

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

Journal

Journal Title*:

ACM Transactions on Sensor Networks
Journal's URL:


Download URL
for the article:

http://delivery.acm.org/10.1145/1170000/1167941/p444-funke.pdf?key1=1167941&key2=5916704711&coll=GUIDE&dl=GUIDE&CFID=17134845&CFTOKEN=44242062
Language:

English

Publisher

Publisher's
Name:

ACM
Publisher's URL:


Publisher's
Address:

New York, USA
ISSN:


Vol, No, pp, Date

Volume*:

2
Number:

3

Publishing Date:

2006

Pages*:

444-453
Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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.

URL for the Abstract:

http://doi.acm.org/10.1145/1167941

Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{FKesselmanMeyerS2006,
AUTHOR = {Funke, Stefan and Kesselman, Alexander and Meyer, Ulrich and Segal, Michael},
 TITLE = {A Simple Improved Distributed Algorithm for Minimum {CDS} in Unit Disk Graphs},
 JOURNAL = {ACM Transactions on Sensor Networks},
 PUBLISHER = {ACM},
 YEAR = {2006},
 NUMBER = {3},
 VOLUME = {2},
 PAGES = {444--453},
 ADDRESS = {New York, USA},
}

Entry last modified by Anja Becker, 05/19/2011
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Christine Kiesel		Created
03/16/2007 09:12:47 PM
Revisions
4.
3.
2.
1.
0.		Editor(s)
Anja Becker
Anja Becker
Anja Becker
Uwe Brahm
Uwe Brahm		Edit Dates
19.05.2011 10:44:48
08.02.2008 14:45:21
08.02.2008 14:40:43
2007-04-27 13:19:40
16.03.2007 21:19:07
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section