On the Distributed Complexity of Computing Maximal Matchings
Authors:
- Michal HanckowiakMHMichal Hanckowiak
- Michal KaronskiMKMichal Karonski
- Alessandro PanconesiAPAlessandro Panconesi
- 1 January 2001
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 15 (1) , 41-57
Abstract
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.Keywords
This publication has 23 references indexed in Scilit:
- Nearly optimal distributed edge coloring in O(log log n) roundsRandom Structures & Algorithms, 1997
- An improvement on parallel computation of a maximal matchingInformation Processing Letters, 1995
- Low‐diameter graph decomposition is in NCRandom Structures & Algorithms, 1994
- Removing randomness in parallel computation without a processor penaltyJournal of Computer and System Sciences, 1993
- Locality in Distributed Graph AlgorithmsSIAM Journal on Computing, 1992
- Parallel Symmetry-Breaking in Sparse GraphsSIAM Journal on Discrete Mathematics, 1988
- Efficient parallel algorithms for edge coloring problemsJournal of Algorithms, 1987
- Deterministic coin tossing with applications to optimal parallel list rankingInformation and Control, 1986
- An improved parallel algorithm for maximal matchingInformation Processing Letters, 1986
- Chromatic number, girth and maximal degreeDiscrete Mathematics, 1978