06112264

j

06112264 Guibas, Leonidas Milosavljevi\'c, Nikola Motskin, Arik Connected dominating sets on dynamic geometric graphs. Comput. Geom. 46, No. 2, 160-172 (2013). 2013 Elsevier Science B.V. (North-Holland), Amsterdam EN connected dominating set unit-ball graph dynamic graph

doi:10.1016/j.comgeo.2012.01.004

Summary: We propose algorithms for efficiently maintaining a constant-approximate minimum connected dominating set (MCDS) of a geometric graph under node insertions and deletions, and under node mobility. Assuming that two nodes are adjacent in the graph if and only if they are within a fixed geometric distance, we show that an $O(1)$-approximate MCDS of a graph in $\Bbb{R}^{d}$ with $n$ nodes can be maintained in $O(log^{2d}n)$ time per node insertion or deletion. We also show that $\Omega(n)$ time per operation is necessary to maintain exact MCDS. This lower bound holds even for $d=1$, even for randomized algorithms, and even when running time is amortized over a sequence of insertions/deletions, or over continuous motion. The crucial fact is that a single operation may affect the entire exact solution, while an approximate solution is affected only in a small neighborhood of the node that was inserted or deleted. In the approximate case, we show how to compute these local changes by a few range searching queries and a few bichromatic closest pair queries.