We show that maximal matchings can be computed deterministically in O(log4n ) 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.
No takes yet. Share an insight, caveat, or question.
Hańćkowiak et al. (2001) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: