A Massively Parallel Algorithm for Minimum Weight Vertex Cover
Nilis, Daan · Repository for Publications and Research Data (ETH Zurich) · 2019
We present a massively parallel algorithm, with near-linear memory per machine, that computes a (2+ε)-approximation of minimum-weight vertex cover in O(log log d) rounds, where d is the average degree of the input graph.