Revisiting Connected Dominating Sets: An Almost Optimal Local Information Algorithm

Samir Khuller, Sheng Yang*

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

In this paper we consider the classical connected dominating set 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 information 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 information greedy algorithm uses significantly less knowledge about the graph, and can be useful in a variety of contexts. However, a fundamental question remained—can we get a local information 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)
Pages (from-to)2592-2605
Number of pages14
JournalAlgorithmica
Volume81
Issue number6
DOIs
StatePublished - Jun 1 2019

Keywords

  • Approximation algorithms
  • Dominating sets
  • Graph algorithms
  • Local information algorithms

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Revisiting Connected Dominating Sets: An Almost Optimal Local Information Algorithm'. Together they form a unique fingerprint.

  • Cite this