License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2019.35
URN: urn:nbn:de:0030-drops-102741
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10274/
Go to the corresponding LIPIcs Volume Portal

Hjuler, Niklas ; Italiano, Giuseppe F. ; Parotsidis, Nikos ; Saulpic, David

Dominating Sets and Connected Dominating Sets in Dynamic Graphs

pdf-format:
LIPIcs-STACS-2019-35.pdf (0.5 MB)

Abstract

In this paper we study the dynamic versions of two basic graph problems: Minimum Dominating Set and its variant Minimum Connected Dominating Set. For those two problems, we present algorithms that maintain a solution under edge insertions and edge deletions in time O(Delta * polylog n) per update, where Delta is the maximum vertex degree in the graph. In both cases, we achieve an approximation ratio of O(log n), which is optimal up to a constant factor (under the assumption that P != NP). Although those two problems have been widely studied in the static and in the distributed settings, to the best of our knowledge we are the first to present efficient algorithms in the dynamic setting.
As a further application of our approach, we also present an algorithm that maintains a Minimal Dominating Set in O(min(Delta, sqrt{m})) per update.

BibTeX - Entry

@InProceedings{hjuler_et_al:LIPIcs:2019:10274,
  author =	{Niklas Hjuler and Giuseppe F. Italiano and Nikos Parotsidis and David Saulpic},
  title =	{{Dominating Sets and Connected Dominating Sets in Dynamic Graphs}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{35:1--35:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Rolf Niedermeier and Christophe Paul},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10274},
  doi =		{10.4230/LIPIcs.STACS.2019.35},
  annote =	{Keywords: Dominating Set, Connected Dominating Set, Dynamic Graph Algorithms}
}

Keywords: Dominating Set, Connected Dominating Set, Dynamic Graph Algorithms
Collection: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Issue Date: 2019
Date of publication: 12.03.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI