Round Compression for Parallel Matching Algorithms
From MaRDI portal
Publication:5130844
DOI10.1137/18M1197655zbMath1445.68331WikidataQ126835252 ScholiaQ126835252MaRDI QIDQ5130844
Slobodan Mitrović, Krzysztof Onak, Piotr Sankowski, Jakub Łącki, Aleksander Mądry, Artur Czumaj
Publication date: 29 October 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25)
Related Items (2)
Equivalence classes and conditional hardness in massively parallel computations ⋮ Component stability in low-space massively parallel computation
Uses Software
Cites Work
- Unnamed Item
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- An improved parallel algorithm for maximal matching
- A fast and simple randomized parallel algorithm for maximal matching
- Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
- On the Distributed Complexity of Computing Maximal Matchings
- Maintaining a large matching and a small vertex cover
- On distributing symmetric streaming computations
- A faster distributed algorithm for computing maximal matchings deterministically
- Communication complexity of approximate matching in distributed graphs
- Sorting, Searching, and Simulation in the MapReduce Framework
- Improved Distributed Approximate Matching
- Fully Dynamic Matching in Bipartite Graphs
- The price of being near-sighted
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Faster Fully Dynamic Matchings with Small Approximation Ratios
- Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time
- Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
- Communication Steps for Parallel Query Processing
- Optimal bounds for decision problems on the CRCW PRAM
- Optimal deterministic routing and sorting on the congested clique
- 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
- Parallel algorithms for geometric graph problems
- Paths, Trees, and Flowers
- New deterministic approximation algorithms for fully dynamic matching
- Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
- Approximating matching size from random streams
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
This page was built for publication: Round Compression for Parallel Matching Algorithms
