DISC 2009 · 23rd International Symposium on Distributed Computing, Elche, Spain, September 2009 · doi:10.1007/978-3-642-04355-0_21
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.
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