文章基本信息

标题：Dominating Sets and Connected Dominating Sets in Dynamic Graphs
本地全文：下载
作者：Niklas Hjuler ; Giuseppe F. Italiano ; Nikos Parotsidis 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2019
卷号：126
页码：1-17
DOI：10.4230/LIPIcs.STACS.2019.35
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Dominating Set; Connected Dominating Set; Dynamic Graph Algorithms