Local 3-approximation algorithms for weighted dominating set and vertex cover in quasi unit-disk graphs
Marja Hassinen, Valentin Polishchuk, Jukka Suomela · 2008
We present a simple 3-approximation algorithm for minimum-weight dominating set and minimum-weight vertex cover in unit-disk graphs and quasi unit-disk graphs in which each node knows its coordinates. The algorithm is local: the output of a node depends solely on the input within its constantradius neighbourhood. The local horizon of the algorithm is small, both in the worst case and on average.