hide
Free keywords:
-
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.
