A better constant-factor approximation for weighted dominating set in unit disk graph

Ambühl C, Erlebach T, Mihalák M, Nunkesser M (2006) Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. In: Proceedings of the 9th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2006). LNCS, vol 4110. Springer, Berlin, pp 3–14

Baker BS (1994) Approximation algorithms for NP-complete problems on planar graphs. J Assoc Comput Mach 41(1):153–180

Bar-Yehuda R, Moran S (1984) On approximation problems related to the independent set and vertex cover problem. Discrete Appl Math 9:1–10

Clark BN, Colbourn CJ, Johnson DS (1990) Unit disk graphs. Discrete Math 86:165–177

Dai WF, Gao M, Stojmenovic I (2002) On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks. J Commun Netw 4(1):59–70

Feige U (1996) A Threshold of lnn for approximating set cover. In: Proc. 28th ACM symposium on theory of computing. ACM, New York, pp 314–318

Garey MR, Johnson DS (1979) Computers and intractability. In: A guide to the theory of NP completeness. Freeman, New York

Guha S, Khuller S (1999) Improved methods for approximating node weighted Steiner trees and connected dominating sets. Inf Comput 150(1):57–74

Hochbaum DS, Maass W (1985) Approximation schemes for covering and packing problems in image processing and VLSI. J Assoc Comput Mach 32(1):130–136

Hunt HB III, Marathe MV, Radhakrishnan V, Ravi SS, Rosenkrantz DJ, Stearns RE (1998) NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs. J Algorithms 26(2):238–274

Lichtenstein D (1982) Planar formulae and their uses. SIAM J Comput 11(2):329–343

Marathe MV, Breu H, Hunt HB III, Ravi SS, Rosenkrantz DJ (1995) Simple heuristics for unit disk graphs. Networks 25:59–68

Vazirani VV (2001) Approximation algorithms. Springer, Berlin

Wang Y, Li XY (2005) Distributed low-cost backbone formation for wireless ad hoc networks. In: Proceedings of the 6th ACM international symposium on mobile ad hoc networking and computing (MobiHoc 2005), pp 2–13

Wu J, Li H (1999) On calculating connected dominating set for efficient routing in ad-hoc wireless networks. In: Proc. of the 3rd international workshop on discrete algorithms and methods for mobile computing and commun, pp 7–14