On the Distributed Complexity of Computing Maximal Matchings
Michał Hańćkowiak, Michał Karoński, Alessandro Panconesi · SIAM Journal on Discrete Mathematics · 2001
We show that maximal matchings can be computed deterministically in O(log 4 n ) rounds in the synchronous, message-passing model of computation. This is one of the very few cases known of a nontrivial graph structure, and the only "classical" one, which can be computed distributively in polylogarithmic time without recourse to randomization.