A local 2-approximation algorithm for the vertex cover problem
- Åstrand, Matti
- Floreen, Patrik
- Polishchuk, Valentin
- Rybicki, Joel
- Suomela, Jukka
- Uitto, Jara
Publication date
January 2009
DOI Publisher
Springer Science and Business Media LLCAbstract
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.Peer reviewe
Add to ORKG