Approximation Algorithms for Connected Dominating Sets Export

@article{citeulike:2855827, abstract = {Abstract. \ \  The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to be either in the dominating set, or adjacent to some vertex in the dominating set. We focus on the related 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 as well. This problem arises in network testing, as well as in wireless communication. Two polynomial time algorithms that achieve approximation factors of 2H(Δ)+2 and H(Δ)+2 are presented, where Δ 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 at least one of its neighbors visited. We also consider a generalization of the problem to the weighted case, and give an algorithm with an approximation factor of (c n +1) \ln n where c n ln k is the approximation factor for the node weighted Steiner tree problem (currently c n = 1.6103 ). We also consider the more general problem of finding a connected dominating set of a specified subset of vertices and provide a polynomial time algorithm with a (c+1) H(Δ) +c-1 approximation factor, where c is the Steiner approximation ratio for graphs (currently c = 1.644 ).}, author = {Guha, S. and Khuller, S.}, citeulike-article-id = {2855827}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/PL00009201}, day = {21}, doi = {10.1007/PL00009201}, journal = {Algorithmica}, keywords = {ecds-journal}, month = {April}, number = {4}, pages = {374--387}, posted-at = {2008-07-15 17:23:43}, priority = {2}, title = {Approximation Algorithms for Connected Dominating Sets}, url = {http://dx.doi.org/10.1007/PL00009201}, volume = {20}, year = {1998} }

TY - JOUR ID - citeulike:2855827 L3 - citeulike-article-id:2855827 N2 - Abstract.    The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex is required to be either in the dominating set, or adjacent to some vertex in the dominating set. We focus on the related 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 as well. This problem arises in network testing, as well as in wireless communication. Two polynomial time algorithms that achieve approximation factors of 2H(Δ)+2 and H(Δ)+2 are presented, where Δ 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 at least one of its neighbors visited. We also consider a generalization of the problem to the weighted case, and give an algorithm with an approximation factor of (c n +1) \ln n where c n ln k is the approximation factor for the node weighted Steiner tree problem (currently c n = 1.6103 ). We also consider the more general problem of finding a connected dominating set of a specified subset of vertices and provide a polynomial time algorithm with a (c+1) H(Δ) +c-1 approximation factor, where c is the Steiner approximation ratio for graphs (currently c = 1.644 ). IS - 4 JF - Algorithmica EP - 387 TI - Approximation Algorithms for Connected Dominating Sets VL - 20 SP - 374 KW - ecds-journal AU - Guha, S AU - Khuller, S PY - 1998/04/21/ UR - http://dx.doi.org/10.1007/PL00009201 ER -