Fetching the paper…
Reading the bibliography…
We present improved deterministic distributed algorithms for a number of well-studied matching problems, which are simpler, faster, more accurate, and/or more general than their known counterparts.
Edge dominating sets in graphs
Mihalis Yannakakis and Fanica Gavril · 1980
Earlier work this paper cites.
A fast and simple randomized parallel algorithm for the maximal independent set problem
Noga Alon, László Babai, and Alon Itai · 1986
Earlier work this paper cites.
A fast and simple randomized parallel algorithm for maximal matching
Amos Israeli and Alon Itai · 1986
Earlier work this paper cites.
An improved parallel algorithm for maximal matching
Amos Israeli and Yossi Shiloach · 1986
Earlier work this paper cites.
A simple parallel algorithm for the maximal independent set problem
Michael Luby · 1986
Earlier work this paper cites.
Distributive graph algorithms - global solutions from local data
Nathan Linial · 1987
Earlier work this paper cites.
Locality in distributed graph algorithms
Nathan Linial · 1992
Earlier work this paper cites.
Julius petersen’s theory of regular graphs
Henry Martyn Mulder · 1992
Earlier work this paper cites.
On the distributed complexity of computing maximal matchings
Michał Hańćkowiak, Michał Karonski, and Alessandro Panconesi · 1998
Earlier work this paper cites.
On the distributed complexity of computing maximal matchings
Michał Hańćkowiak, Michał Karonski, and Alessandro Panconesi · 1998
Earlier work this paper cites.
A faster distributed algorithm for computing maximal matchings deterministically
Michał Hańćkowiak, Michał Karoński, and Alessandro Panconesi · 1999
Earlier work this paper cites.
Some simple distributed algorithms for sparse networks
Alessandro Panconesi and Romeo Rizzi · 2001
Earlier work this paper cites.
Distributed algorithm for better approximation of the maximum matching
Andrzej Czygrinow and Michał Hańćkowiak · 2003
Earlier work this paper cites.
Distributed algorithm for approximating the maximum matching
Andrzej Czygrinow, Michał Hańćkowiak, and Edyta Szymańska · 2004
Cited alongside, same era.
A fast distributed algorithm for approximating the maximum matching
Andrzej Czygrinow, Michał Hańćkowiak, and Edyta Szymańska · 2004
Cited alongside, same era.
A simpler linear time 2/3- ε \varepsilon approximation for maximum weight matching
Seth Pettie and Peter Sanders · 2004
Cited alongside, same era.
Distributed weighted matching
Mirjam Wattenhofer and Roger Wattenhofer · 2004
Cited alongside, same era.
The price of being near-sighted
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer · 2006
Cited alongside, same era.
Distributed approximate matching
Zvi Lotker, Boaz Patt-Shamir, and Adi Rosen · 2007
Cited alongside, same era.
Space-efficient local computation algorithms
Noga Alon, Ronitt Rubinfeld, Shai Vardi, and Ning Xie · 2012
Later among the works it cites.
The locality of distributed symmetry breaking
Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider · 2012
Later among the works it cites.
Distributed maximal matching: Greedy is optimal
Juho Hirvonen and Jukka Suomela · 2012
Later among the works it cites.
Deterministic stateless centralized local algorithms for bounded degree graphs
Guy Even, Moti Medina, and Dana Ron · 2014
Later among the works it cites.
Linear-in-delta lower bounds in the local model
Mika Göös, Juho Hirvonen, and Jukka Suomela · 2014
Later among the works it cites.
Improved distributed approximate matching
Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie · 2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
Michal Parnas and Dana Ron · 2007
Cited alongside, same era.
Improved distributed approximate matching
Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie · 2008
Cited alongside, same era.
Distributed fractional packing and maximum weighted b-matching via tail-recursive duality
Christos Koufogiannakis and Neal E. Young · 2009
Cited alongside, same era.
Fast primal-dual distributed algorithms for scheduling and matching problems
Alessandro Panconesi and Mauro Sozio · 2010
Cited alongside, same era.
Distributed algorithms for edge dominating sets
Jukka Suomela · 2010
Cited alongside, same era.
Fast local computation algorithms
Ronitt Rubinfeld, Gil Tamir, Shai Vardi, and Ning Xie · 2011
Cited alongside, same era.
An exponential separation between randomized and deterministic complexity in the LOCAL model
Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie · 2016
Later among the works it cites.
An improved distributed algorithm for maximal independent set
Mohsen Ghaffari · 2016
Later among the works it cites.
Distributed ( Δ {\Delta} + 1)-coloring in sublogarithmic rounds
David G. Harris, Johannes Schneider, and Hsin-Hao Su · 2016
Later among the works it cites.
Local computation: Lower and upper bounds
Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer · 2016
Later among the works it cites.
On the complexity of local distributed graph problems
Mohsen Ghaffari, Fabian Kuhn, and Yannic Maus · 2017
Closest in time.
Distributed degree splitting, edge coloring, and orientations
Mohsen Ghaffari and Hsin-Hao Su · 2017
Closest in time.