Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
type: Item
instance of: scholarly article
title: Improved MPC algorithms for MIS, matching, and coloring on trees and beyond
zbMATH Open document ID: 1540.68177
author: Mohsen Ghaffari
author: Christoph Grunau
author: Ce Jin
publication date: 2023-11-02T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W10
zbMATH DE Number: 7760523
zbMATH Keywords: massively parallel computation
zbMATH Keywords: MIS
zbMATH Keywords: matching
zbMATH Keywords: coloring
MaRDI profile type: Publication
cites work: A fast and simple randomized parallel algorithm for the maximal independent set problem
cites work: Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs
cites work: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
cites work: The Locality of Distributed Symmetry Breaking
cites work: Brief Announcement: MapReduce Algorithms for Massive Trees
cites work: Massively Parallel Computation of Matching and MIS in Sparse Graphs
cites work: Breaking the linear-memory barrier in MPC: fast MIS on trees with strongly sublinear memory
cites work: Round Compression for Parallel Matching Algorithms
cites work: Distributed MIS via All-to-All Communication
cites work: Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
cites work: Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
cites work: Sorting, Searching, and Simulation in the MapReduce Framework
cites work: Q5417679
cites work: Local Computation
cites work: Locality in Distributed Graph Algorithms
cites work: A Simple Parallel Algorithm for the Maximal Independent Set Problem
cites work: Decomposition of Finite Graphs Into Forests
cites work: Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
DOI: 10.4230/LIPICS.DISC.2020.34
description: scientific article; zbMATH DE number 7760523