SIAM Journal on Discrete Mathematics · 2001 · 135 citations · 13 references
ComputingComputer ScienceMathematicsAlgorithmsMessage PassingTheory Of ComputationComputational ComplexityDistributed ComputingGraph AlgorithmsGraph TheoryMatching TheoryRandomized ComputationComplexityComputational Complexity Of Graph AlgorithmsDistributed ComplexityDistributed Matching AlgorithmsGraph MatchingMatching AlgorithmsMatching ProblemsMessage-passing Models
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.
13
Locality in Distributed Graph Algorithms
Nathan Linial · SIAM Journal on Computing · 1992 · 885 citations
Moni Naor, Larry Stockmeyer · SIAM Journal on Computing · 1995 · 317 citations