de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Konferenzbeitrag

Connected Dominating Sets on Dynamic Geometric Graphs

MPG-Autoren
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45051

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


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