Marja Hassinen · Valentin Polishchuk · Jukka Suomela

Local 3-approximation algorithms for weighted dominating set and vertex cover in quasi unit-disk graphs

LOCALGOS 2008 · 2nd International Workshop on Localized Algorithms and Protocols for Wireless Sensor Networks, Santorini Island, Greece, June 2008

authors’ version

Abstract

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.

Publication

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

ISBN 978-90-9023209-6

Links

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.