Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
436200 | Theoretical Computer Science | 2009 | 10 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics