Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
From MaRDI portal
Publication:5002618
DOI10.4230/LIPIcs.APPROX-RANDOM.2017.15zbMath1467.68224arXiv1702.02559OpenAlexW2962933030MaRDI QIDQ5002618
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1702.02559
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)
Related Items
Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Improved bounds for randomized preemptive online matching ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ Unnamed Item ⋮ Depth First Search in the Semi-streaming Model ⋮ Optimal lower bounds for matching and vertex cover in dynamic graph streams ⋮ Multi-pass streaming algorithms for monotone submodular function maximization
Cites Work
- Unnamed Item
- Unnamed Item
- Submodular maximization meets streaming: matchings, matroids, and more
- Linear programming in the semi-streaming model with application to the maximum matching problem
- Bipartite matching in the semi-streaming model
- On graph problems in a semi-streaming model
- Maximum Matching in Semi-streaming with Few Passes
- Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
- Streaming Algorithms for Submodular Function Maximization
- Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
- Maximum Matching in Turnstile Streams
- Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
- Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
- On Estimating Maximum Matching Size in Graph Streams
- A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model
- Weighted Matching in the Semi-Streaming Model
- Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
- Approximating matching size from random streams
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Better bounds for matchings in the streaming model
This page was built for publication: Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams