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.

Authors

• Decheng Dai
• Changyuan Yu Baidu Inc.

Keywords

• Weighted unit disk graph
• Dominating set
• Approximation algorithm