Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | 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