Matti Åstrand · Patrik Floréen · Valentin Polishchuk · Joel Rybicki · Jukka Suomela · Jara Uitto

A local 2-approximation algorithm for the vertex cover problem

DISC 2009 · 23rd International Symposium on Distributed Computing, Elche, Spain, September 2009 · doi:10.1007/978-3-642-04355-0_21

authors’ version publisher’s version

Abstract

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

Publication

Idit Keidar (Ed.): Distributed Computing, 23rd International Symposium, DISC 2009, Elche, Spain, September 23–25, 2009, Proceedings, volume 5805 of Lecture Notes in Computer Science, pages 191–205, Springer, Berlin, 2009

ISBN 978-3-642-04354-3

Links

© Springer 2009 — The original publication is available at www.springerlink.com.

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.