A 5 + ε-approximation algorithm for minimum weighted dominating set in unit disk graph

摘要

We study the minimum weight dominating set problem in weighted unit disk graph, and give a polynomial time algorithm with approximation ratio 5 + ε, improving the previous best result of 6 + ε in [Yaochun Huang, Xiaofeng Gao, Zhao Zhang, Weili Wu, A better constant-factor approximation for weighted dominating set in unit disk graph, J. Comb. Optim. (ISSN: 1382-6905) (2008) 1573-2886. (Print) (Online)]. Combining the common technique used in the above mentioned reference, we can compute a minimum weight connected dominating set with approximation ratio 9 + ε, beating the previous best result of 10 + ε in the same work.