Revisiting connected dominating sets: An optimal local algorithm?

Samir Khuller; Sheng Yang

doi:10.1109/ITA.2018.8503201

Revisiting connected dominating sets: An optimal local algorithm?

Samir Khuller, Sheng Yang

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	2018 Information Theory and Applications Workshop, ITA 2018
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9781728101248
DOIs	https://doi.org/10.1109/ITA.2018.8503201
State	Published - Oct 23 2018
Event	2018 Information Theory and Applications Workshop, ITA 2018 - San Diego, United States Duration: Feb 11 2018 → Feb 16 2018

Publication series

Name	2018 Information Theory and Applications Workshop, ITA 2018

Other

Other	2018 Information Theory and Applications Workshop, ITA 2018
Country/Territory	United States
City	San Diego
Period	2/11/18 → 2/16/18

ASJC Scopus subject areas

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

Access to Document

10.1109/ITA.2018.8503201

Cite this

@inproceedings{fbae6d19caa6464aa997facdb37a67f2,

title = "Revisiting connected dominating sets: An optimal local algorithm?",

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.",

author = "Samir Khuller and Sheng Yang",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 2018 Information Theory and Applications Workshop, ITA 2018 ; Conference date: 11-02-2018 Through 16-02-2018",

year = "2018",

month = oct,

day = "23",

doi = "10.1109/ITA.2018.8503201",

language = "English (US)",

series = "2018 Information Theory and Applications Workshop, ITA 2018",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "2018 Information Theory and Applications Workshop, ITA 2018",

address = "United States",

}

Khuller, S & Yang, S 2018, Revisiting connected dominating sets: An optimal local algorithm? in 2018 Information Theory and Applications Workshop, ITA 2018., 8503201, 2018 Information Theory and Applications Workshop, ITA 2018, Institute of Electrical and Electronics Engineers Inc., 2018 Information Theory and Applications Workshop, ITA 2018, San Diego, United States, 2/11/18. https://doi.org/10.1109/ITA.2018.8503201

Revisiting connected dominating sets: An optimal local algorithm? / Khuller, Samir; Yang, Sheng.
2018 Information Theory and Applications Workshop, ITA 2018. Institute of Electrical and Electronics Engineers Inc., 2018. 8503201 (2018 Information Theory and Applications Workshop, ITA 2018).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Revisiting connected dominating sets

T2 - 2018 Information Theory and Applications Workshop, ITA 2018

AU - Khuller, Samir

AU - Yang, Sheng

PY - 2018/10/23

Y1 - 2018/10/23

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85057280898&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85057280898&partnerID=8YFLogxK

U2 - 10.1109/ITA.2018.8503201

DO - 10.1109/ITA.2018.8503201

M3 - Conference contribution

AN - SCOPUS:85057280898

T3 - 2018 Information Theory and Applications Workshop, ITA 2018

BT - 2018 Information Theory and Applications Workshop, ITA 2018

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 11 February 2018 through 16 February 2018

ER -

Revisiting connected dominating sets: An optimal local algorithm?

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this