Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
From MaRDI portal
Publication:6535033
DOI10.4230/lipics.disc.2020.34zbMath1540.68177MaRDI QIDQ6535033
Christoph Grunau, Ce Jin, Mohsen Ghaffari
Publication date: 2 November 2023
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (1)
Cites Work
- Unnamed Item
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- Breaking the linear-memory barrier in MPC: fast MIS on trees with strongly sublinear memory
- Sorting, Searching, and Simulation in the MapReduce Framework
- Local Computation
- The Locality of Distributed Symmetry Breaking
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Locality in Distributed Graph Algorithms
- Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
- Brief Announcement: MapReduce Algorithms for Massive Trees
- Round Compression for Parallel Matching Algorithms
- Massively Parallel Computation of Matching and MIS in Sparse Graphs
- Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
- 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
- Distributed MIS via All-to-All Communication
- Decomposition of Finite Graphs Into Forests
This page was built for publication: Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
