2026-08-07T10:54:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6634 2024-03-06T10:38:33Z ddc:004 open_access

Revisiting Connected Dominating Sets: An Optimal Local Algorithm? Khuller, Samir Yang, Sheng graph algorithms approximation algorithms dominating sets local information algorithms In this paper we consider the classical Connected Dominating Set (CDS) problem. Twenty years ago, Guha and Khuller developed two algorithms for this problem - a centralized greedy approach with an approximation guarantee of H(D) +2, and a local greedy approach with an approximation guarantee of 2(H(D)+1) (where H() is the harmonic function, and D is the maximum degree in the graph). A local greedy algorithm uses significantly less information about the graph, and can be useful in a variety of contexts. However, a fundamental question remained - can we get a local greedy algorithm with the same performance guarantee as the global greedy algorithm without the penalty of the multiplicative factor of "2" in the approximation factor? In this paper, we answer that question in the affirmative. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Samir Khuller and Sheng Yang 2016 Is Part Of LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2016.11 urn:nbn:de:0030-drops-66340 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.11 eng https://creativecommons.org/licenses/by/3.0/legalcode