Streaming graph algorithms in the massively parallel computation model

DOI10.1145/3662158.3662770MaRDI QIDQ6971908zbMATH OpenFDO

Authors Artur Czumaj, Gopinath Mishra, A. Mukherjee

Publication date 13 June 2025

Full work available at URL https://doi.org/10.1145/3662158.3662770

zbMATH Keywords

connectivitymatchingminimum spanning treeMPCstreaming

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Cites work

• A Framework for Adversarially Robust Streaming Algorithms
• Batch-parallel Euler tour trees
• Communication steps for parallel query processing
• Component Stability in Low-Space Massively Parallel Computation
• Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs
• Data streams: algorithms and applications.
• Exponentially faster massively parallel maximal matching
• scientific article; zbMATH DE number 6297759 (Why is no real title available?)
• scientific article; zbMATH DE number 7053292 (Why is no real title available?)
• scientific article; zbMATH DE number 7651141 (Why is no real title available?)
• scientific article; zbMATH DE number 7788513 (Why is no real title available?)
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Lessons from the congested clique applied to MapReduce
• Maximum matching in turnstile streams
• Maximum matchings in dynamic graph streams and the simultaneous communication model
• Near-optimal massively parallel graph connectivity
• On estimating maximum matching size in graph streams
• On graph problems in a semi-streaming model
• Optimal dynamic distributed MIS
• Optimal lower bounds for distributed and streaming spanning forest computation
• Parallel algorithms for geometric graph problems
• Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
• Parallel graph connectivity in log diameter rounds
• Reachability and distances under multiple changes
• Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference Guide
• 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
• Tight bounds for single-pass streaming complexity of the set cover problem
• Walking randomly, massively, and efficiently

This page was built for publication: Streaming graph algorithms in the massively parallel computation model

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