TY - GEN

T1 - Revisiting connected dominating sets

T2 - 19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2016 and the 20th International Workshop on Randomization and Computation, RANDOM 2016

AU - Khuller, Samir

AU - Yang, Sheng

N1 - Funding Information:
This work is supported by NSF grant CCF 1217890.

PY - 2016/9/1

Y1 - 2016/9/1

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.

KW - Approximation Algorithms

KW - Dominating Sets

KW - Graph Algorithms

KW - Local Information Algorithms

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

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

U2 - 10.4230/LIPIcs.APPROX-RANDOM.2016.11

DO - 10.4230/LIPIcs.APPROX-RANDOM.2016.11

M3 - Conference contribution

AN - SCOPUS:84990855862

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 19th International Workshop, APPROX 2016 and 20th International Workshop, RANDOM 2016

A2 - Jansen, Klaus

A2 - Mathieu, Claire

A2 - Rolim, Jose D. P.

A2 - Umans, Chris

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Y2 - 7 September 2016 through 9 September 2016

ER -