LOCALGOS 2008 · 2nd International Workshop on Localized Algorithms and Protocols for Wireless Sensor Networks, Santorini Island, Greece, June 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 constant-radius neighbourhood. The local horizon of the algorithm is small, both in the worst case and on average.
Koen Langendoen (Ed.): DCOSS ’08, June 11 – 14, Santorini Island, Greece, Adjunct workshop proceedings, WITS, IWSNE, CPS-CA, WEWSN, LOCALGOS, ProSense/WiDeploy, pages V.9–V.12, 2008