zbMATH — the first resource for mathematics

New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs. (English) Zbl 1209.68389
Summary: Given a node-weighted graph, the Minimum-Weighted Dominating Set (MWDS) problem is to find a minimum-weighted vertex subset such that, for any vertex, it is contained in this subset or it has a neighbor contained in this set. And the Minimum-Weighted Connected Dominating Set (MWCDS) problem is to find a MWDS such that the graph induced by this subset is connected. In this paper, we study these two problems on a unit disk graph. A \((4 +\varepsilon )\)-approximation algorithm for an MWDS based on a dynamic programming algorithm for a Min-Weight Chromatic Disk Cover is presented. Meanwhile, we also propose a \((1 +\varepsilon )\)-approximation algorithm for the connecting part by showing a polynomial-time approximation scheme for a Node-Weighted Steiner Tree problem when the given terminal set is \(c\)-local and thus obtain a \((5+\varepsilon)\)-approximation algorithm for an MWCDS.

68R10 Graph theory (including graph drawing) in computer science
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68W25 Approximation algorithms
Full Text: DOI
[1] Ambühl, C.; Erlebach, T.; Mihalák, M.; Nunkesser, M., Constant-factor approximation for minimum-weight (connect) dominating sets in unit disk graphs, Lecture notes in computer science, 4110, 3-14, (2006) · Zbl 1148.05308
[2] Baker, B.S., Approximation algorithm for NP-complete problems on planar graphs, Journal of the ACM, 41, 153-180, (1994) · Zbl 0807.68067
[3] Chen, D.; Du, D.Z.; Hu, X.D.; Lin, G.H.; Wang, L.; Xue, G., Approximation for Steiner trees with minimum number of Steiner points, Theoretical computer science, 262, 83-99, (2001) · Zbl 0983.68140
[4] B. Das, V. Bharghavan, Routing in ad hoc networks using minimum connected dominating sets, in: International Conference on Communications, 1997
[5] Dai, D.; Yu, C., A \((5 + \varepsilon)\)-approximation algorithm for minimum weighted dominating set in unit disk graph, Theoretical computer science, (2009) · Zbl 1162.68042
[6] Garey, M.R.; Johnson, D.S., Computers and intractability. A guide to the theory of NP-completeness, (1979), Freeman New York · Zbl 0411.68039
[7] Guha, S.; Khuller, S., Improved methods of approximating node weighted Steiner tree and connected dominating sets, Information and computation, 150, 57-74, (1999) · Zbl 1045.68594
[8] Hochbaum, D.S.; Maass, W., Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM, 32, 130-136, (1985) · Zbl 0633.68027
[9] Huang, Y.; Gao, X.; Zhang, Z.; Wu, W., A better constant-factor approximation for weighted dominating set in unit disk graph, Journal of combinatorial optimization, (2008)
[10] Hwang, F.K.; Richards, D.S., Steiner tree problems, Networks, 22, 55-89, (1992) · Zbl 0749.90082
[11] Lichtenstein, D., Planar formulae and their uses, SIAM journal on computing, 11, 329-343, (1982) · Zbl 0478.68043
[12] S. Ni, Y. Tseng, Y. Chen, J. Sheu, The broadcast storm problem in a mobile ad hoc network, in: MOBICOM’99, Washington, USA, August 1999, pp. 152-162 · Zbl 1012.68980
[13] G. Robins, J.S. Salowe, On the maximum degree of minimum spanning trees, in: Proceedings of the ACM Symposium on Computational Geometry, 1994, pp. 250-258
[14] Wang, L.; Jiang, T., An approximation scheme for some Steiner tree problem in the plane, Networks, 28, 187-193, (1996) · Zbl 0873.90106
[15] Wu, W.; Du, H.; Jia, X.; Li, Y.; Huang, S.C.H., Minimum connected dominating sets and maximal independent sets in unit disk graphs, Theoretical computer science, 352, 1-7, (2006) · Zbl 1086.68107
[16] Zou, F.; Li, X.; Kim, D.; Wu, W., Node-weighted Steiner tree approximation in unit disk graphs, Journal of combination optimization, (2009) · Zbl 1184.90146
[17] Zhang, Z.; Huang, Y.; Gao, X.; Wu, W., A better constant-factor approximation for weighted dominating set in unit disk graphs, Journal of combinatorial optimization, 1573-2886, (2008)
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.