Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space

DOI10.1145/3451992MaRDI QIDQ5032024zbMATH OpenOpenAlexWikidataFDO

Authors P. Davies, Artur Czumaj, M. Parter

Publication date 16 February 2022

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.05390, http://wrap.warwick.ac.uk/153774/7/WRAP-graph-sparsification-derandomizing-massively-parallel-computation-low%20space-Czumaj-2021.pdf

zbMATH Keywords

derandomizationmassively parallel computationmaximal independent setmaximal matchingsparsification

Mathematics Subject Classification ID

Computer science (68-XX)

Recommendations

• Massively Parallel Computation of Matching and MIS in Sparse Graphs
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory

Cited in

(10)

• Equivalence classes and conditional hardness in massively parallel computations
• Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
• Massively Parallel Computation of Matching and MIS in Sparse Graphs
• Superfast coloring in CONGEST via efficient color sampling
• Component stability in low-space massively parallel computation
• Derandomization with pseudorandomness
• Massively parallel computation in a heterogeneous regime
• Brief announcement: Massively parallel ruling set made deterministic
• Parallel derandomization for coloring
• Optimal (degree+1)-coloring in congested clique

This page was built for publication: Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space

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