2026-07-22T12:57:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10274 2024-03-06T10:45:41Z ddc:004 open_access

Dominating Sets and Connected Dominating Sets in Dynamic Graphs Hjuler, Niklas Italiano, Giuseppe F. Parotsidis, Nikos Saulpic, David Dominating Set Connected Dominating Set Dynamic Graph Algorithms 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Niklas Hjuler and Giuseppe F. Italiano and Nikos Parotsidis and David Saulpic 2019 Is Part Of LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2019.35 urn:nbn:de:0030-drops-102741 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.35 eng https://creativecommons.org/licenses/by/3.0/legalcode