Revisiting connected dominating sets: An optimal local algorithm?

Samir Khuller, Sheng Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

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(δ)+2, and a local greedy approach with an approximation guarantee of 2(H(δ) + 1) (where H() is the harmonic function, and δ 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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016
EditorsKlaus Jansen, Claire Mathieu, Jose D. P. Rolim, Chris Umans
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770187
DOIs
StatePublished - Sep 1 2016
Event19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016 - Paris, France
Duration: Sep 7 2016Sep 9 2016

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume60
ISSN (Print)1868-8969

Other

Other19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016
CountryFrance
CityParis
Period9/7/169/9/16

Keywords

  • Approximation Algorithms
  • Dominating Sets
  • Graph Algorithms
  • Local Information Algorithms

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Revisiting connected dominating sets: An optimal local algorithm?'. Together they form a unique fingerprint.

Cite this