Approximation Algorithms for Connected Dominating Sets
| dc.contributor.author | Guha, Sudipto | en_US |
| dc.contributor.author | Khuller, Samir | en_US |
| dc.date.accessioned | 2004-05-31T22:40:08Z | |
| dc.date.available | 2004-05-31T22:40:08Z | |
| dc.date.created | 1996-06 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.abstract | 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 some node in the dominating set. We focus on the question of finding a {\em connected dominating set} of minimum size, where the graph induced by vertices in the dominating set is required to be {\em connected} as well. This problem arises in network testing, as well as in wireless communication. Two polynomial time algorithms that achieve approximation factors of $O(H(\Delta))$ are presented, where $\Delta$ 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 study a generalization of the problem when the vertices have weights, and give an algorithm which achieves a performance ratio of $3 \ln n$. We also consider the more general problem of finding a connected dominating set of a specified subset of vertices and provide an $O(H(\Delta))$ approximation factor. To prove the bound we also develop an optimal approximation algorithm for the unit node weighted Steiner tree problem. (Also cross-referenced as UMIACS-TR-96-47) | en_US |
| dc.format.extent | 210492 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/830 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3660 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-96-47 | en_US |
| dc.title | Approximation Algorithms for Connected Dominating Sets | en_US |
| dc.type | Technical Report | en_US |