AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS   Info

AG Audience

English

30 Minutes

Saarbrücken

A connected dominating set (CDS) of an undirected graph $G=(V, E)$ is a subset of $V$ adjacent to all of $V$ that also induces a connected subgraph of $G$. Motivated by the problem of computing a communication backbone in a wireless network, we constrain $G$ to be an intersection graph of unit balls in $R^d$, for fixed $d$. In this setting, the problem of computing a CDS of minimum size is still NP-hard, but admits a PTAS.

We study the problem of maintaining an approximately minimum CDS under vertex insertions and deletions. We show that under rectilinear ($\ell_1$ and $\ell_\infty$) norms, an $O(1)$-approximation can be maintained in polylog-time per update and near-linear space.

This is joint work with Leonidas Guibas and Arik Motskin.

Nikola Milosavljevic

--email hidden

passcode not visible

logged in users only