Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model
From MaRDI portal
Publication:6130326
DOI10.1007/s00453-023-01190-4arXiv2109.05946OpenAlexW3201331607MaRDI QIDQ6130326
Publication date: 2 April 2024
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2109.05946
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Weighted matching in the semi-streaming model
- On graph problems in a semi-streaming model
- Maximum Matching in Semi-streaming with Few Passes
- Maximum matchings in bipartite graphs via strong spanning trees
- Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
- Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
- On Estimating Maximum Matching Size in Graph Streams
- Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
- A (2+ϵ)-Approximation for Maximum Weight Matching in the Semi-streaming Model
- Planar Matching in Streams Revisited
- Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
- A simple augmentation method for matchings with applications to streaming algorithms
- The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs
- Approximating matching size from random streams
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Maximum matching and a polyhedron with 0,1-vertices
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Better bounds for matchings in the streaming model
- Graph streaming lower bounds for parameter estimation and property testing via a streaming XOR lemma
- A framework for dynamic matching in weighted graphs
This page was built for publication: Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model
