TY - GEN

T1 - Approximation algorithms for connected dominating sets

AU - Guha, Sudipto

AU - Khuller, Samir

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1996.

PY - 1996

Y1 - 1996

N2 - The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to either be in the dominating set, or adjacent to at least one node in the dominating set. We focus on the question of finding a connected dominating set of minimum size, where the graph induced by vertices in the dominating set is required to be connected. This problem arises in network testing, as well as in wireless communication. Two polynomial time algorithms that achieve approximation factors of O(H(A)) are presented, where A is the maximum degree, and H is the harmonic function. This question also arises in relation to the traveling tourist problem, where one is looking for the shortest tour such that each vertex is either visited, or has one of its neighbors visited. We study a generalization of the problem when the vertices have weights, and give an algorithm which achieves a performance ratio of 3 Inn. We also consider the more general problem of finding a connected dominating set of a specified set of vertices and provide a 3 Inn approximation factor. To prove the bound we also develop an optimal approximation algorithm for the unit node weighted Steiner tree problem.

AB - The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to either be in the dominating set, or adjacent to at least one node in the dominating set. We focus on the question of finding a connected dominating set of minimum size, where the graph induced by vertices in the dominating set is required to be connected. This problem arises in network testing, as well as in wireless communication. Two polynomial time algorithms that achieve approximation factors of O(H(A)) are presented, where A is the maximum degree, and H is the harmonic function. This question also arises in relation to the traveling tourist problem, where one is looking for the shortest tour such that each vertex is either visited, or has one of its neighbors visited. We study a generalization of the problem when the vertices have weights, and give an algorithm which achieves a performance ratio of 3 Inn. We also consider the more general problem of finding a connected dominating set of a specified set of vertices and provide a 3 Inn approximation factor. To prove the bound we also develop an optimal approximation algorithm for the unit node weighted Steiner tree problem.

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

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

U2 - 10.1007/3-540-61680-2_55

DO - 10.1007/3-540-61680-2_55

M3 - Conference contribution

AN - SCOPUS:84958034163

SN - 3540616802

SN - 9783540616801

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 179

EP - 193

BT - Algorithms - ESA 1996 - 4th Annual European Symposium, Proceedings

A2 - Diaz, Josep

A2 - Serna, Maria

PB - Springer Verlag

T2 - 4th European Symposium on Algorithms, ESA 1996

Y2 - 25 September 1996 through 27 September 1996

ER -