# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Connected Dominating Sets on Dynamic Geometric Graphs

##### 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.