|
On the Distributed Complexity of Computing Maximal Matchings
Micha December 1997 |
|
On the Distributed Complexity of Computing Maximal Matchings
Micha December 1997 |
Abstract: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. |
Hanckowiak