A Fast Distributed Algorithm for Approximating the Maximum Matching

摘要

We present a distributed approximation algorithm that computes in every graph G a matching M of size at least 2/3β(G), where β(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].