2018 · 103 citations · 35 references
ComputingComputer ScienceAlgorithmsParallel AlgorithmsParallel ComputingAlgorithm AnalysisApproximation AlgorithmsData ParallelismParallel ArchitecturesParallel Complexity TheoryParallel Computing SystemsApproximation In Parallel ComputationMatchingMatching AlgorithmsMaximum Independent Set ApproximationMaximum Matching ApproximationParallel Graph AlgorithmsParallel Matching AlgorithmsVertex Cover Approximation
We present O(loglog n) -round algorithms in the Massively Parallel Computation (MPC) model, with Õ (n) memory per machine, that compute a maximal independent set, a 1+ε approximation of maximum matching, and a 2+εapproximation of minimum vertex cover, for any n-vertex graph and any constant \eps>0. These improve the state of the art as follows:
35
Sanjay Ghemawat · Communications of the ACM · 2008 · 18.5K citations · Full text
Spark: cluster computing with working sets
Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin et al. · 2010 · 4.2K citations
Michael Isard, Mihai Budiu, Yuan Yu et al. · 2007 · 2.5K citations
A Simple Parallel Algorithm for the Maximal Independent Set Problem
Michael Luby · SIAM Journal on Computing · 1986 · 1.1K citations