Cheng, XiuzhenHuang, XiaoLi, DeyingDu, Ding-Zhu2020-09-022020-09-022002-01-22https://hdl.handle.net/11299/215507A 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. The 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 $(1+1/s)$-approximation for the minimum connected dominating set in unit-disk graphs, running in time $n^{O((slog s)^2)}$.en-USReport