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...
Main Authors: | , , , , |
---|---|
Other Authors: | |
Format: | Article |
Language: | English |
Published: |
ACM
2021
|
Online Access: | https://hdl.handle.net/1721.1/129790 |