Fetching the paper…
Reading the bibliography…
Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring.
Chromatic number, girth and maximal degree
B. Bollobás · 1978
Earlier work this paper cites.
Extremal graph theory
B. Bollobás · 1978
Earlier work this paper cites.
Another advantage of free choice: Completely asynchronous agreement protocols
M. Ben-Or · 1983
Earlier work this paper cites.
Randomized Byzantine generals
M. O. Rabin · 1983
Earlier work this paper cites.
An asynchronous ( n − 1 ) / 3 (n-1)/3 -resilient consensus protocol
G. Bracha · 1984
Earlier work this paper cites.
Impossibility of distributed consensus with one faulty process
M. J. Fischer, N. A. Lynch, and M. Paterson · 1985
Earlier work this paper cites.
A lower bound on probabilistic algorithms for distributive ring coloring
M. Naor · 1991
Earlier work this paper cites.
Locality in distributed graph algorithms
N. Linial · 1992
Earlier work this paper cites.
What can be computed locally?
M. Naor and L. J. Stockmeyer · 1995
Earlier work this paper cites.
On the complexity of distributed network decomposition
A. Panconesi and A. Srinivasan · 1996
Earlier work this paper cites.
On the distributed complexity of computing maximal matchings
M. Hańćkowiak, M. Karoński, and A. Panconesi · 2001
Earlier work this paper cites.
Some simple distributed algorithms for sparse networks
A. Panconesi and R. Rizzi · 2001
Cited alongside, same era.
What cannot be computed locally!
F. Kuhn, T. Moscibroda, and R. Wattenhofer · 2004
Cited alongside, same era.
Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
L. Barenboim and M. Elkin · 2010
Cited alongside, same era.
Local computation: Lower and upper bounds
F. Kuhn, T. Moscibroda, and R. Wattenhofer · 2010
Cited alongside, same era.
An optimal maximal independent set algorithm for bounded-independence graphs
J. Schneider and R. Wattenhofer · 2010
Cited alongside, same era.
Super-fast 3 3 -ruling sets
K. Kothapalli and S. V. Pemmaraju · 2012
Cited alongside, same era.
Brief announcement: Super-fast t t -ruling sets
T. Bisht, K. Kothapalli, and S. V. Pemmaraju · 2014
Later among the works it cites.
Distributed algorithms for the Lovász local lemma and graph coloring
K.-M. Chung, S. Pettie, and H.-H. Su · 2014
Later among the works it cites.
Regular graphs of large girth and arbitrary degree
X. Dahan · 2014
Later among the works it cites.
Deterministic ( Δ + 1 ) (\Delta+1) -coloring in sublinear (in Δ \Delta ) time in static, dynamic and faulty networks
L. Barenboim · 2015
Later among the works it cites.
( 2 Δ − 1 ) (2\Delta-1) -edge coloring is much easier than maximal matching in the distributed setting
M. Elkin, S. Pettie, and H. H. Su · 2015
Later among the works it cites.
Distributed algorithms for coloring triangle-free graphs
S. Pettie and H.-H. Su · 2015
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Introduction to the Theory of Computation
M. Sipser · 2012
Cited alongside, same era.
Byzantine agreement in polynomial expected time
V. King and J. Saia · 2013
Cited alongside, same era.
Toward more localized local algorithms: removing assumptions concerning global knowledge
A. Korman, J.-S. Sereni, and L. Viennot · 2013
Cited alongside, same era.
Distributed ( Δ + 1 ) (\Delta+1) -coloring in linear (in Δ \Delta ) time
L. Barenboim, M. Elkin, and F. Kuhn · 2014
Cited alongside, same era.
A distributed ( 2 + ϵ ) (2+\epsilon) -approximation for vertex cover in O ( log Δ / ϵ log log Δ ) {O}(\log{\Delta}/\epsilon\log\log{\Delta}) rounds
R. Bar-Yehuda, K. Censor-Hillel, and G. Schwartzman
Cited in the paper.
Later among the works it cites.
The locality of distributed symmetry breaking
L. Barenboim, M. Elkin, S. Pettie, and J. Schneider · 2016
Closest in time.
A lower bound for the distributed Lovász local lemma
S. Brandt, O. Fischer, J. Hirvonen, B. Keller, T. Lempiäinen, J. Rybicki, J. Suomela, and J. Uitto · 2016
Closest in time.
An improved distributed algorithm for maximal independent set
M. Ghaffari · 2016
Closest in time.
Distributed ( Δ + 1 ) (\Delta+1) -coloring in sublogarithmic rounds
D. Harris, J. Schneider, and H.-H. Su · 2016
Closest in time.