A 5+ϵ-approximation algorithm for minimum weighted dominating set in unit disk graph

Christoph Ambühl, Thomas Erlebach, Matús Mihalák, Marc Nunkesser, Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs, in: Proc. APPROX-RANDOM, 2006, pp. 3–14 Huang, 2008, A better constant-factor approximation for weighted dominating set in unit disk graph, J. Comb. Optim., 1573 Lichtenstein, 1982, Planar formulae and their uses, SIAM J. Comput., 11, 329, 10.1137/0211025 M.V. Marathe, H. Breu, H.B. Hunt III, S.S. Ravi, D.J. Rosenkrantz, Simple heuristics for unit disk graphs, Networks, 25, pp. 59–86 Hunt, 1998, NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, J. Algorithms, 26, 238, 10.1006/jagm.1997.0903 Clark, 1990, Unit disk graphs, Discrete Math., 86, 165, 10.1016/0012-365X(90)90358-O M.R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN: 0-7167-1044-7 Bar-Yehuda, 1984, On approximation problems related to the independent set and vertex cover problem, Discrete Appl. Math., 9, 1, 10.1016/0166-218X(84)90086-6 Vazirani, 2001 Uriel Feige, A Threshold of lnn for Approximating Set Cover, in: Proc. 28th ACM Symposium on Theory of Computing, 1996, pp. 314–318 Guha, 1999, Improved methods for approximation node weighted Steiner trees and connected dominating sets, Inform. Comput., 150, 57, 10.1006/inco.1998.2754 Khaled M. Alzoubi, Pengjun Wan, Ophir Frieder, Message-optimal connected dominating sets in mobile ad hoc networks, in: Proceedings of the 3rd ACM Interational Symposium on Mobile Ad Hoc Networking and Computing, June 9–11, 2002, pp. 157–164 Jie Wu, Hailan Li, On calculating connected dominating set for efficient routing in ad hoc wireless networks, in: Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Seattle, Washington, USA, August 20, 1999, pp. 7–14