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.APPROX-RANDOM.2016.11
URN: urn:nbn:de:0030-drops-66340
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6634/
Go to the corresponding LIPIcs Volume Portal

Khuller, Samir ; Yang, Sheng

Revisiting Connected Dominating Sets: An Optimal Local Algorithm?

pdf-format:
LIPIcs-APPROX-RANDOM-2016-11.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{khuller_et_al:LIPIcs:2016:6634,
  author =	{Samir Khuller and Sheng Yang},
  title =	{{Revisiting Connected Dominating Sets: An Optimal Local Algorithml}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{11:1--11:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Klaus Jansen and Claire Mathieu and Jos{\'e} D. P. Rolim and Chris Umans},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6634},
  URN =		{urn:nbn:de:0030-drops-66340},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.11},
  annote =	{Keywords: graph algorithms, approximation algorithms, dominating sets, local information algorithms}
}

Keywords: graph algorithms, approximation algorithms, dominating sets, local information algorithms
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Issue Date: 2016
Date of publication: 06.09.2016

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