Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
DOI10.1016/j.tcs.2020.10.007zbMath1467.68205OpenAlexW3093384812MaRDI QIDQ2215966
Jara Uitto, Manuela Fischer, Sebastian F. Brandt
Publication date: 15 December 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.10.007
treessparse graphslinear-memory barriermassively parallel computation (MPC)maximal independent set (MIS)strongly sublinear memory
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Online algorithms; streaming algorithms (68W27)
Uses Software
Cites Work
- Unnamed Item
- Breaking the linear-memory barrier in MPC: fast MIS on trees with strongly sublinear memory
- MIS on trees
- Sorting, Searching, and Simulation in the MapReduce Framework
- The Locality of Distributed Symmetry Breaking
- Minimum Dominating Set Approximation in Graphs of Bounded Arboricity
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- An algorithmic approach to the Lovász local lemma. I
- An Improved Distributed Algorithm for Maximal Independent Set
- Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
- Communication Steps for Parallel Query Processing
- Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
- Round compression for parallel matching algorithms
- Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
- Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
- Parallel algorithms for geometric graph problems
- Fast randomized algorithms for distributed edge coloring
This page was built for publication: Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory
