Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover

We present O(log log 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 ε &g...

Full description

Bibliographic Details
Main Authors: Ghaffari, Mohsen, Gouleakis, Themistoklis, Konrad, Christian, Mitrović, Slobodan, Rubinfeld, Ronitt
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:English
Published: ACM 2021
Online Access:https://hdl.handle.net/1721.1/129790

Similar Items

Similar Items