Distributed and parallel algorithms for weighted vertex cover and other covering problems
Christos Koufogiannakis, Neal E. Young · 2009
The paper presents distributed and parallel δ-approximation algorithms for covering problems, where δ is the maximum number of variables on which any constraint depends (for example, δ = 2 for VERTEX COVER).