Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation

DOI10.1137/1.9781611975482.99zbMath1431.68133arXiv1807.06251OpenAlexW2951940772MaRDI QIDQ5236283

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1807.06251

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (11)

Equivalence classes and conditional hardness in massively parallel computations ⋮ Deterministic Massively Parallel Connectivity ⋮ Component stability in low-space massively parallel computation ⋮ Maliciously secure massively parallel computation for all-but-one corruptions ⋮ Distributed Symmetry Breaking on Power Graphs via Sparsification ⋮ Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory ⋮ Round Compression for Parallel Matching Algorithms ⋮ Unnamed Item ⋮ Near-optimal clustering in the \(k\)-machine model ⋮ When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time ⋮ Distributed algorithms for matching in hypergraphs

This page was built for publication: Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation