On the Distributed Complexity of Computing Maximal Matchings

Michatex2html_wrap25 Hanckowiak
Michatex2html_wrap25 Karonski
Alessandro Panconesi

December 1997


We show that maximal matchings can be computed deterministically in polylogarithmically many rounds in the synchronous, message-passing model of computation. This is one of the very few cases known of a non-trivial graph structure which can be computed distributively in polylogarithmic time without recourse to randomization

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.