Connected dominating sets on dynamic geometric graphs

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 Rd with n nodes can be maintained in O(log2dn) time per node insertion or deletion. We also show that Ω(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.