A PTAS for minimum connected dominating set in 3-dimensional Wireless sensor networks
Journal of Global Optimization，2008，45（）：451–458 | 2008年12月14日 | doi.org/10.1007/s10898-008-9384-9
When homogeneous sensors are deployed into a three-dimensional space instead of a plane, the mathematical model for the sensor network is a unit ball graph instead of a unit disk graph. It is known that for the minimum connected dominating set in unit disk graph, there is a polynomial time approximation scheme (PTAS). However, that construction cannot be extended to obtain a PTAS for unit ball graph. In this paper, we will introduce a new construction, which gives not only a PTAS for the minimum connected dominating set in unit ball graph, but also improves running time of PTAS for unit disk graph.