Fetching the paper…
Reading the bibliography…
We present $O(\log\log n)$-round algorithms in the Massively Parallel Computation (MPC) model, with $\tilde{O}(n)$ memory per machine, that compute a maximal independent set, a $1+\epsilon$ approximation of maximum matching, and a $2+\epsilon$ approximation of minimum vertex cover, for any $n$-vertex graph and any constant $\epsilon>0$.
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.
MST construction in O( log log n \log\log n ) communication rounds
Zvi Lotker, Elan Pavlov, Boaz Patt-Shamir, and David Peleg · 2003
Earlier work this paper cites.
MapReduce: Simplified data processing on large clusters
Jeffrey Dean and Sanjay Ghemawat · 2004
Earlier work this paper cites.
Finding graph matchings in data streams
Andrew McGregor · 2005
Earlier work this paper cites.
Dryad: Distributed data-parallel programs from sequential building blocks
Michael Isard, Mihai Budiu, Yuan Yu, Andrew Birrell, and Dennis Fetterly · 2007
Earlier work this paper cites.
Distributed approximate matching
Zvi Lotker, Boaz Patt-Shamir, and Adi Rosén · 2009
Earlier work this paper cites.
A model of computation for MapReduce
Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii · 2010
Earlier work this paper cites.
Spark: Cluster computing with working sets
Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica · 2010
Earlier work this paper cites.
Sorting, searching, and simulation in the MapReduce framework
Michael T. Goodrich, Nodari Sitchinava, and Qin Zhang · 2011
Earlier work this paper cites.
Filtering: a method for solving graph problems in MapReduce
Silvio Lattanzi, Benjamin Moseley, Siddharth Suri, and Sergei Vassilvitskii · 2011
Earlier work this paper cites.
The round complexity of distributed sorting
Boaz Patt-Shamir and Marat Teplitsky · 2011
Earlier work this paper cites.
The locality of distributed symmetry breaking
Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider · 2012
Cited alongside, same era.
Greedy sequential maximal independent set and matching are parallel on average
Guy E Blelloch, Jeremy T Fineman, and Julian Shun · 2012
Cited alongside, same era.
Super-fast distributed algorithms for metric facility location
Andrew Berns, James Hegeman, and Sriram V Pemmaraju · 2012
Cited alongside, same era.
“Tri, Tri again”: Finding triangles and small subgraphs in a distributed setting
Danny Dolev, Christoph Lenzen, and Shir Peled · 2012
Cited alongside, same era.
Hadoop: The Definitive Guide
Tom White · 2012
Cited alongside, same era.
Communication steps for parallel query processing
Paul Beame, Paraschos Koutris, and Dan Suciu · 2013
Cited alongside, same era.
Algebraic methods in the congested clique
Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz, and Jukka Suomela · 2015
Later among the works it cites.
Toward optimal bounds in the congested clique: Graph connectivity and MST
James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato · 2015
Later among the works it cites.
An improved distributed algorithm for maximal independent set
Mohsen Ghaffari · 2016
Later among the works it cites.
Mst in log-star rounds of congested clique
Mohsen Ghaffari and Merav Parter · 2016
Later among the works it cites.
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai · 2016
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Optimal deterministic routing and sorting on the congested clique
Christoph Lenzen · 2013
Cited alongside, same era.
Parallel algorithms for geometric graph problems
Alexandr Andoni, Aleksandar Nikolov, Krzysztof Onak, and Grigory Yaroslavtsev · 2014
Cited alongside, same era.
On the power of the congested clique model
Andrew Drucker, Fabian Kuhn, and Rotem Oshman · 2014
Cited alongside, same era.
Lessons from the congested clique applied to MapReduce
James W Hegeman and Sriram V Pemmaraju · 2014
Cited alongside, same era.
Near-constant-time distributed algorithms on a congested clique
James W Hegeman, Sriram V Pemmaraju, and Vivek B Sardeshmukh · 2014
Cited alongside, same era.
Distributed approximation algorithms for weighted shortest paths
Danupon Nanongkai · 2014
Cited alongside, same era.
Janne H Korhonen · 2016
Later among the works it cites.
Randomized composable coresets for matching and vertex cover
Sepehr Assadi and Sanjeev Khanna · 2017
Later among the works it cites.
Simple round compression for parallel vertex cover
Sepehr Assadi · 2017
Later among the works it cites.
Derandomizing local distributed algorithms under bandwidth restrictions
Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman · 2017
Later among the works it cites.
Distributed mis via all-to-all communication
Mohsen Ghaffari · 2017
Later among the works it cites.
Round compression for parallel matching algorithms
Artur Czumaj, Jakub Łącki, Aleksander Mądry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski · 2018
Closest in time.
Tight analysis of parallel randomized greedy mis
Manuela Fischer and Andreas Noever · 2018
Closest in time.
Mst in O (1) rounds of congested clique
Tomasz Jurdziński and Krzysztof Nowicki · 2018
Closest in time.
Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab Mirrokni, and Cliff Stein · 2019
Closest in time.