A polynomial‐time approximation scheme for the minimum‐connected dominating set in ad hoc wireless networks
Xiuzhen Cheng, Xiao Huang, Deying Li, Weili Wu, Ding‐Zhu Du · Networks · 2003
Abstract 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 timenO((slogs)2). © 2003 Wiley Periodicals, Inc.