Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2020) | last year (2019) | two years ago (2018) | Notes URL

Action:

login to update
Options:




Library Locked Library locked




Author, Editor

Author(s):

Guibas, Leonidas
Milosavljevic, Nikola
Motskin, Arik
dblp
dblp
dblp
Not MPG Author(s):

Motskin, Arik
Guibas, Leonidas

Editor(s):





BibTeX cite key*:

Milosavljevic2009

Title, Booktitle

Title*:

Connected Dominating Sets on Dynamic Geometric Graphs


cds_cccg_electronic.pdf (204.36 KB)

Booktitle*:

Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010)

Event, URLs

URL of the conference:

http://www.cs.umanitoba.ca/~cccg2010/

URL for downloading the paper:

http://cccg.ca/proceedings/2010/paper10.pdf

Event Address*:

Winnipeg, Manitoba, Canada
Language:

English

Event Date*
(no longer used):


Organization:

Pacific Institute for Mathematical Studies (PIMS)

Event Start Date:

9 August 2010
Event End Date:

11 August 2010

Publisher

Name*:

CCCG Library

URL:


Address*:

Winnipeg, Canada
Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

27-30

Year*:

2010
VG Wort Pages:


ISBN/ISSN:


Sequence Number:


DOI:




Note, Abstract, ©

Note:

Full version available at:
\url{http://mpi-inf.mpg.de/~nikolam/downloads/cds_cccg_electronic.pdf}

(LaTeX) Abstract:

We propose algorithms for efficiently maintaining a constant-approximate minimum connected dominating set (MCDS) of a geometric graph under node insertions and deletions.
Assuming that two nodes are adjacent in the graph iff they are within a fixed geometric distance, we show that an $O(1)$-approximate MCDS of a graph in $\R^d$ with $n$ nodes can be maintained with polylogarithmic (in $n$) work per node insertion/deletion as compared with $\Omega(n)$ work to maintain the optimal MCDS, even in the weaker kinetic setting. In our approach, we ensure that a topology change caused by inserting or deleting a node only affects the solution in a small neighborhood
of that node, and show that a small set of range queries and bichromatic closest pair queries is then sufficient to efficiently repair the CDS.

Keywords:

Connected Dominating Set, Unit-Ball Graph, Dynamic Computational Geometry

HyperLinks / References / URLs:

\url{http://mpi-inf.mpg.de/~nikolam/downloads/cds_cccg_electronic.pdf}



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Milosavljevic2009,
AUTHOR = {Guibas, Leonidas and Milosavljevic, Nikola and Motskin, Arik},
 TITLE = {Connected Dominating Sets on Dynamic Geometric Graphs},
 BOOKTITLE = {Proceedings of the 22nd Canadian Conference on Computational Geometry (CCCG2010)},
 PUBLISHER = {CCCG Library},
 YEAR = {2010},
 ORGANIZATION = {Pacific Institute for Mathematical Studies (PIMS)},
 PAGES = {27--30},
 ADDRESS = {Winnipeg, Manitoba, Canada},
 NOTE = {Full version available at: \url{http://mpi-inf.mpg.de/~nikolam/downloads/cds_cccg_electronic.pdf}},
}

Entry last modified by Manuel Lamotte-Schubert, 03/28/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)
[Library]		Created
12/15/2010 04:14:49 PM
Revisions
6.
5.
4.
3.
2.		Editor(s)
Manuel Lamotte-Schubert
Manuel Lamotte-Schubert
Anja Becker
Anja Becker
Anja Becker		Edit Dates
28.03.2011 10:57:41
21.03.2011 08:55:22
10.01.2011 12:17:16
10.01.2011 12:14:58
12/15/2010 04:58:38 PM
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section

View attachments here:

File Attachment Icon
cds_cccg_electronic.pdf