
L. Guibas, N. Milosavljevic and A. Motskin. Connected Dominating Sets on Dynamic Geometric Graphs, Canadian Conference on Computational Geometry (CCCG), 2010.
Abstract:
We propose algorithms for efficiently maintaining a constantapproximate
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.
Bibtex:
@inproceedings{gmmcdsdgg10,
author={Leonidas J. Guibas and Nikola Milosavljevic and Arik Motskin},
title={Connected Dominating Sets on Dynamic Geometric Graphs},
booktitle={Proc. of the 22nd Canadian Conference on Computational Geometry (CCCG)},
year={2010}
}

