Massively Parallel Computation of Matching and MIS in Sparse Graphs

DOI10.1145/3293611.3331609MaRDI QIDQ5145260zbMATH OpenOpenAlexFDO

Authors Soheil Behnezhad, Sebastian F. Brandt, Mahsa Derakhshan, Manuela Fischer, Jara Uitto, Mohammad T. Hajiaghayi, Richard Karp

Publication date 20 January 2021

Published in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3293611.3331609

zbMATH Keywords

approximation algorithmsarboricitymassively parallel computationmatchingmaximal independent setsparse graphssublinear memory

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Recommendations

• Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Round compression for parallel matching algorithms
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation

Cited in

(14)

• Equivalence classes and conditional hardness in massively parallel computations
• Parallel algorithms for flexible pattern matching on big graphs
• Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
• Log diameter rounds algorithms for 2-vertex and 2-edge connectivity
• Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
• Maliciously secure massively parallel computation for all-but-one corruptions
• Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
• Distributed-prover interactive proofs
• Sample-and-gather: fast ruling set algorithms in the low-memory MPC model
• Exponential speedup over locality in \textsf{MPC} with optimal memory
• Massively parallel computation in a heterogeneous regime
• Massively parallel algorithms for approximate shortest paths
• Exponentially faster massively parallel maximal matching
• Parallel derandomization for coloring

This page was built for publication: Massively Parallel Computation of Matching and MIS in Sparse Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145260)