A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching

Taisuke Izumi, Naoki Kitamura, Yutaro Yamaguchi

In this paper, we propose a randomized $\tilde{O}(\mu (G))$-round algorithm for the maximum cardinality matching problem in the CONGEST model, where $\mu (G)$ means the maximum size of a…