zbMATH — the first resource for mathematics

A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph. (English) Zbl 1162.68042
Summary: We study the minimum weight dominating set problem in weighted unit disk graph, and give a polynomial time algorithm with approximation ratio \(5+\varepsilon \), improving the previous best result of \(6+\varepsilon \) in [X. Gao, Y. Huang, Z. Zhang and W. Wu, “\((6 + \epsilon )\)-approximation for minimum weight dominating set in unit disk graphs”, Lect. Notes Comput. Sci. 5092, 551–557 (2008; Zbl 1148.05310)]. Combining the common technique used in the above mentioned reference, we can compute a minimum weight connected dominating set with approximation ratio \(9+\varepsilon \), beating the previously best result of \(10+\varepsilon \) in the same work.

68W25 Approximation algorithms
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] 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 · Zbl 1148.05308
[2] Huang, Yaochun; Gao, Xiaofeng; Zhang, Zhao; Wu, Weili, A better constant-factor approximation for weighted dominating set in unit disk graph, J. comb. optim., ISSN: 1382-6905, 1573-2886, (2008), (Print) (Online)
[3] Lichtenstein, David, Planar formulae and their uses, SIAM J. comput., 11, 2, 329-343, (1982) · Zbl 0478.68043
[4] 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 · Zbl 0821.90128
[5] Hunt, H.B.; Marathe, M.V.; Radhakrishman, V.; Ravi, S.S.; Rosenkrantz, D.J.; Stearns, R.E., NC-approximation schemes for NP- and PSPACE-hard problems for geometric graphs, J. algorithms, 26, 2, 238-274, (1998) · Zbl 0894.68105
[6] Clark, B.N.; Colbourn, C.J.; Johnson, D.S., Unit disk graphs, Discrete math., 86, 1-3, 165-177, (1990) · Zbl 0739.05079
[7] 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 · Zbl 0411.68039
[8] Bar-Yehuda, R.; Moran, S., On approximation problems related to the independent set and vertex cover problem, Discrete appl. math., 9, 1-10, (1984) · Zbl 0554.68026
[9] Vazirani, V.V., Approximation algorithms, (2001), Springer · Zbl 1138.90417
[10] Uriel Feige, A Threshold of \(\ln n\) for Approximating Set Cover, in: Proc. 28th ACM Symposium on Theory of Computing, 1996, pp. 314-318 · Zbl 0922.68067
[11] Guha, S.; Khuller, S., Improved methods for approximation node weighted Steiner trees and connected dominating sets, Inform. comput., 150, 1, 57-74, (1999) · Zbl 1045.68594
[12] 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
[13] 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
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.