Publications
Home PageA local 2-approximation algorithm for the vertex cover problem
Conference presentation and article — to appear
| Authors: | Matti Åstrand Patrik Floréen Valentin Polishchuk Joel Rybicki Jukka Suomela Jara Uitto |
| Title: | A local 2-approximation algorithm for the vertex cover problem |
| Conference: | 23rd International Symposium on Distributed Computing (DISC) Elche, Spain September 2009 |
| Links: | authors’ version © Springer-Verlag 2009 — The original publication is available at www.springerlink.com. |
| 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. |
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.