Revisiting connected dominating sets: An optimal local algorithm?

Samir Khuller, Sheng Yang

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

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 publication2018 Information Theory and Applications Workshop, ITA 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781728101248
DOIs
StatePublished - Oct 23 2018
Event2018 Information Theory and Applications Workshop, ITA 2018 - San Diego, United States
Duration: Feb 11 2018Feb 16 2018

Publication series

Name2018 Information Theory and Applications Workshop, ITA 2018

Other

Other2018 Information Theory and Applications Workshop, ITA 2018
CountryUnited States
CitySan Diego
Period2/11/182/16/18

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Information Systems
  • Software
  • Information Systems and Management
  • Theoretical Computer Science

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

Cite this