# zbMATH — the first resource for mathematics

A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks. (English) Zbl 1031.05092
Summary: A connected dominating set in a graph is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum-connected dominating set is such a vertex subset with minimum cardinality. An application in ad hoc wireless networks requires the study of the minimum-connected dominating set in unit-disk graphs. In this paper, we design a ($$1 + 1/s$$)-approximation for the minimum-connected dominating set in unit-disk graphs, running in time $$n^{O((s \log s)^2)}$$.

##### MSC:
 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C85 Graph algorithms (graph-theoretic aspects)
Full Text: