MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

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
Conference URL::
http://www.cs.umanitoba.ca/~cccg2010/
Downloading URL:
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
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

File Attachment Icon
cds_cccg_electronic.pdf