A fast distributed algorithm for approximating the maximum matching
Andrzej Czygrinow, Michał Hańćkowiak, Edyta Szymańska · 2004
Abstract. We present a distributed approximation algorithm that computes in every graph G a matching M of size at least 2 β(G), where 3 β(G) is the size of a maximum matching in G. The algorithm runs in O(log 4 |V (G)|) rounds in the synchronous, message passing model of computation and matches the best known asymptotic complexity for computing a maximal matching in the same protocol. This improves the running time of an algorithm proposed recently by the authors in [2]. 1