Performance Analysis and Improvement for the Construction of MCDS Problem in 3D Space
In this paper, we discuss the problem of finding a minimum connected dominating set (MCDS) in 3-dimensional space, where the communication model is a unit ball graph (UBG). MCDS in UBG is proved to be an NP-complete problem, and currently the best approximation is 14.937 in [1]. However, their projection method during the approximation deduction process is incorrect, which overthrows its final bound completely. As a consequence, in this paper we will first propose a new projection method to overcome their problem, illustrate the cardinality upper bound of independent points in a graph (which will be used to analyze the approximation ratio), and then optimize the algorithms to select MCDS with prune techniques. The major technique we use is an adaptive jitter scheme, which solves the open question in this area.