Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings

Salwa Faour, Marc Fuchs, Fabian Kuhn

We provide CONGEST model algorithms for approximating minimum weighted vertex cover and the maximum weighted matching. For bipartite graphs, we show that a $(1+\epsilon )$-approx…