Abstract
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.
This work has been supported in part by the National Natural Science Foundation of China (Grant No.61202024), Shanghai Pujiang Program (No.13PJ1403900), Shanghai Educational Development Foundation (Chenguang Grant No.12CG09), and the Natural Science Foundation of Shanghai (Grant No.12ZR1445000).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Kim, D., Zhang, Z., Li, X., Wang, W., Wu, W., Du, D.Z.: A better approximation algorithm for computing connected dominating sets in unit ball graphs. IEEE Trans. Mob. Comput. 9(8), 1108–1118 (2010)
Kouider, M., Vestergaard, P.D., et al.: Generalized connected domination in graphs. Theoret. Comput. Sci. 8(1), 57–64 (2006)
Gaspers, S., Liedloff, M., et al.: A branch-and-reduce algorithm for finding a minimum independent dominating set. Theoret. Comput. Sci. 14(1), 29–42 (2012)
Wang, X., Li, P.: Improved data association method in binocular vision-SLAM. In: ICICTA, vol. 2, pp. 502–505. IEEE (2010)
Yang, D.: An immunity-based ant colony optimization topology control algorithm for 3D wireless sensor networks. Sens. Transducers J. 150(3), 125–129 (2013)
Wan, P.J., Alzoubi, K.M., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. In: INFOCOM, vol. 3, pp. 1597–1604. IEEE (2002)
Wu, W., Du, H., Jia, X., Li, Y., Huang, S.C.H.: Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theoret. Comput. Sci. 352(1), 1–7 (2006)
Gao, X., Wang, Y., Li, X., Wu, W.: Analysis on theoretical bounds for approximating dominating set problems. Discret. Math. Algorithms Appl. 1(01), 71–84 (2009)
Li, M., Wan, P.J., Yao, F.: Tighter approximation bounds for minimum CDS in unit disk graphs. Algorithmica 61(4), 1000–1021 (2011)
Du, Y.L., Du, H.W.: A new bound on maximum independent set and minimum connected dominating set in unit disk graphs. J. Combin. Optim. 1–7 (2013). doi: 10.1007/s10878-013-9690-0
Hansen, J.C., Schmutz, E.: Comparison of two CDS algorithms on random unit ball graphs. In: ALENEX/ANALCO, pp. 206–211 (2005)
Butenko, S., Ursulenko, O.: On minimum connected dominating set problem in unit-ball graphs. Preprint Submitted to Elsevier Science (2007)
Zhong, X., Wang, J., Hu, N.: Connected dominating set in 3-dimensional space for ad hoc network. In: WCNC, pp. 3609–3612. IEEE (2007)
Zou, F., Li, X., Kim, D., Wu, W.: Construction of minimum connected dominating set in 3-dimensional wireless network. In: Li, Y., Huynh, D.T., Das, S.K., Du, D.-Z. (eds.) WASA 2008. LNCS, vol. 5258, pp. 134–140. Springer, Heidelberg (2008)
Du, D.-Z., Wan, P.-J.: Connected Dominating Set: Theory And Applications. Springer Optimization and Its Applications, vol. 77. Springer, Heidelberg (2012)
Zong, C.: Sphere Packings. Springer, New York (1999)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Li, J., Gao, X., Chen, G., Gao, F., Ding, L. (2014). Performance Analysis and Improvement for the Construction of MCDS Problem in 3D Space. In: Zhang, Z., Wu, L., Xu, W., Du, DZ. (eds) Combinatorial Optimization and Applications. COCOA 2014. Lecture Notes in Computer Science(), vol 8881. Springer, Cham. https://doi.org/10.1007/978-3-319-12691-3_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-12691-3_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12690-6
Online ISBN: 978-3-319-12691-3
eBook Packages: Computer ScienceComputer Science (R0)