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

Workshop presentation

Authors:	Marja Hassinen, Valentin Polishchuk, and Jukka Suomela
Title:	Local 3-approximation algorithms for weighted dominating set and vertex cover in quasi unit-disk graphs
Workshop:	2nd International Workshop on Localized Algorithms and Protocols for Wireless Sensor Networks (LOCALGOS), Santorini Island, Greece, June 2008
Proceedings:	Koen Langendoen (Ed.): DCOSS ’08. June 11 – 14, Santorini Island, Greece. Adjunct workshop proceedings. WITS, IWSNE, CPS-CA, WEWSN, LOCALGOS, ProSense/WiDeploy
	ISBN: 978-90-9023209-6 pages V.9–V.12
Links:	authors’ version
	presentation, 14 June 2008
	workshop · conference
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.

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.