×

zbMATH — the first resource for mathematics

A better constant-factor approximation for weighted dominating set in unit disk graph. (English) Zbl 1184.05090
Summary: This paper presents a \((10+\varepsilon)\)-approximation algorithm to compute minimum-weight connected dominating set (MWCDS) in unit disk graph. MWCDS is to select a vertex subset with minimum weight for a given unit disk graph, such that each vertex of the graph is contained in this subset or has a neighbor in this subset. Besides, the subgraph induced by this vertex subset is connected. Our algorithm is composed of two phases: the first phase computes a dominating set, which has approximation ratio \(6 + \varepsilon\) (\(\varepsilon\) is an arbitrary positive number), while the second phase connects the dominating sets computed in the first phase, which has approximation ratio 4.

MSC:
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C22 Signed and weighted graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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 · Zbl 1148.05308
[2] Baker BS (1994) Approximation algorithms for NP-complete problems on planar graphs. J Assoc Comput Mach 41(1):153–180 · Zbl 0807.68067
[3] Bar-Yehuda R, Moran S (1984) On approximation problems related to the independent set and vertex cover problem. Discrete Appl Math 9:1–10 · Zbl 0554.68026 · doi:10.1016/0166-218X(84)90086-6
[4] Clark BN, Colbourn CJ, Johnson DS (1990) Unit disk graphs. Discrete Math 86:165–177 · Zbl 0739.05079 · doi:10.1016/0012-365X(90)90358-O
[5] 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
[6] 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 · Zbl 0922.68067
[7] Garey MR, Johnson DS (1979) Computers and intractability. In: A guide to the theory of NP completeness. Freeman, New York · Zbl 0411.68039
[8] Guha S, Khuller S (1999) Improved methods for approximating node weighted Steiner trees and connected dominating sets. Inf Comput 150(1):57–74 · Zbl 1096.68683 · doi:10.1006/inco.1998.2754
[9] 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 · Zbl 0633.68027
[10] 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 · Zbl 0894.68105 · doi:10.1006/jagm.1997.0903
[11] Lichtenstein D (1982) Planar formulae and their uses. SIAM J Comput 11(2):329–343 · Zbl 0478.68043 · doi:10.1137/0211025
[12] Marathe MV, Breu H, Hunt HB III, Ravi SS, Rosenkrantz DJ (1995) Simple heuristics for unit disk graphs. Networks 25:59–68 · Zbl 0821.90128 · doi:10.1002/net.3230250205
[13] Vazirani VV (2001) Approximation algorithms. Springer, Berlin · Zbl 0985.65058
[14] 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
[15] 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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.