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