PTAS for Minimum Connected Dominating Set in Unit Ball Graph

摘要

When sensors are deployed into a space instead of a plane, the mathematical model for the sensor network should be a unit ball graph instead of a unit disk graph. It has been known that the minimum connected dominating set in unit disk graph has a polynomial time approximation scheme (PTAS). Could we extend the construction of this PTAS for unit disk graphs to unit ball graphs? The answer is NO. 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.