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