A simple augmentation method for matchings with applications to streaming algorithms
From MaRDI portal
Publication:5005178
DOI10.4230/LIPIcs.MFCS.2018.74OpenAlexW2889431167MaRDI QIDQ5005178
Publication date: 4 August 2021
Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2018.74
Related Items
Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model, Optimal lower bounds for matching and vertex cover in dynamic graph streams
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Superlinear lower bounds for multipass graph processing
- Improved algorithms for latency minimization in wireless networks
- Weighted matching in the semi-streaming model
- Bipartite matching in the semi-streaming model
- On graph problems in a semi-streaming model
- Maximum Matching in Semi-streaming with Few Passes
- Maximum Matching in Turnstile Streams
- A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model
- Approximating Semi-matchings in Streaming and in Two-Party Communication
- Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
- Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover
- Tight Bounds for Graph Problems in Insertion Streams
- 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
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Better bounds for matchings in the streaming model
