de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Connected Dominating Sets on Dynamic Geometric Graphs

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45051

Milosavljevic,  Nikola
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Guibas, L., Milosavljevic, N., & Motskin, A. (2010). Connected Dominating Sets on Dynamic Geometric Graphs. In Proceedings of the 22nd Canadian Conference on Computational Geometry (pp. 27-30). Winnipeg, Canada: CCCG Library. Retrieved from http://cccg.ca/proceedings/2010/paper10.pdf.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-162D-8
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.