Breaking the linear-memory barrier in MPC: fast MIS on trees with strongly sublinear memory

DOI10.1016/J.TCS.2020.10.007MaRDI QIDQ2215966zbMATH OpenOpenAlexFDO

Authors Manuela Fischer, Jara Uitto, 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

zbMATH Keywords

linear-memory barriermassively parallel computation (MPC)maximal independent set (MIS)sparse graphsstrongly sublinear memorytrees

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40)

Recommendations

• Breaking the linear-memory barrier in MPC: fast MIS on trees with strongly sublinear memory
• scientific article; zbMATH DE number 4030978
• scientific article; zbMATH DE number 7774301
• Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
• MSO Queries on Tree Decomposable Structures Are Computable with Linear Delay
• Bounded treewidth and space-efficient linear algebra
• On a sublinear time parallel construction of optimal binary search trees
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth

Cites work

• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Simple 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
• Breaking the linear-memory barrier in MPC: fast MIS on trees with strongly sublinear memory
• Communication steps for parallel query processing
• Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs
• Fast randomized algorithms for distributed edge coloring (extended abstract)
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Minimum dominating set approximation in graphs of bounded arboricity
• MIS on trees
• Parallel algorithms for geometric graph problems
• Round compression for parallel matching algorithms
• Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
• Sorting, searching, and simulation in the MapReduce framework
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
• The locality of distributed symmetry breaking

Cited in

(8)

• Equivalence classes and conditional hardness in massively parallel computations
• Breaking the linear-memory barrier in MPC: fast MIS on trees with strongly sublinear memory
• Brief announcement: MapReduce algorithms for massive trees
• Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
• Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Sparsifying distributed algorithms with ramifications in massively parallel computation and centralized local computation
• Improved MPC algorithms for MIS, matching, and coloring on trees and beyond

Describes a project that uses

Uses Software

• MapReduce

This page was built for publication: Breaking the linear-memory barrier in \(\mathsf{MPC}\): fast \(\mathsf{MIS}\) on trees with strongly sublinear memory

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