Abstract
In the minimum weighted dominating set problem (MWDS), we are given a unit disk graph with non-negative weight on each vertex. The MWDS seeks a subset of the vertices of the graph with minimum total weight such that each vertex of the graph is either in the subset or adjacent to some nodes in the subset. A weight function is called smooth, if the ratio of the weights of any two adjacent nodes is upper bounded by a constant. MWDS is known to be NP-hard. In this paper, we give the first polynomial time approximation scheme (PTAS) for MWDS with smooth weights on unit disk graphs, which achieves a (1+ε)-approximation for MWDS, for any ε>0.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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: Proc APPROX-RANDOM, pp 3–14
Bharghavan V, Das B (1997) Routing in ad hoc networks using minimum connected dominating sets. In: Proc of international conference on communications’97, Montreal, Canada (June 1997), pp 376–380
Clark BN, Colbourn CJ, Johnson DS (1990) Unit disk graphs. Discrete Math 86:165–177
Dai D, Yu C (2009) A 5+ε-approximation algorithm for minimum weighted dominating set in unit disk graph. Theor Comput Sci 410:756–765
Gfeller B, Vicari E (2007) A faster distributed approximation scheme for the connected dominating set problems for growth-bounded graphs. In: Kranakis TE, Opatrny J (eds) ADHOC-NOW 2007. LNCS, vol 4686. Springer, Berlin, pp 59–73
Guha S, Khuller S (1998) Approximation algorithms for connected dominating sets. Algorithmica 20(4):374–387
Huang YC, Gao XF, Zhang Z, Wu WL (2008) A better constant-factor approximation for weighted dominating set in unit disk graph. J Comb Optim, 1573–2886
Nieberg T, Hurink J (2006) A PTAS for the minimum dominating set problem in unit disk graphs. In: Erlebach T, Persiano G (eds) WAOA 2005. LNCS, vol 3879. Springer, Berlin, pp 296–306
Wan P, Alzoubi KM, Frieder O (2002) Distributed construction of connected dominating set in wireless ad hoc networks. In: Proc Infocom
Wang Y, Wang W, Li X-Y (2005) Distributed low-cost backbone formation for wireless ad hoc networks. In: Proc 6th ACM international symposium on mobile ad hoc networking and computing (MOBIHOC), pp 2–13
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Zhu, X., Wang, W., Shan, S. et al. A PTAS for the minimum weighted dominating set problem with smooth weights on unit disk graphs. J Comb Optim 23, 443–450 (2012). https://doi.org/10.1007/s10878-010-9357-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-010-9357-z