Distributed algorithm for approximating the maximum matching (Q1887042)

The authors present an \(O(\log^6 n)\)-time distributed algorithm computing a matching of size at least \(\frac{2}{3}| M^*| \) where \(M^*\) is a maximum matching and \(n\) is the number of vertices of the input graph. The approximation factor \(2/3\) relies on a theorem due to \textit{T. Fischer, A. V. Goldberg, D. J. Haglin} and \textit{S. Plotkin} [``Approximating matchings in parallel'', Inf. Process. Lett. 46, 115--118 (1993; Zbl 0784.68065)].