Deterministic algorithms for maximum matching on general graphs in the semi-streaming model
From MaRDI portal
(Redirected from Publication:5090980)
Recommendations
- Bipartite matching in the semi-streaming model
- Maximum matching in two, three, and a few more passes over graph streams
- Maximum matching in semi-streaming with few passes
- A \((2+\epsilon)\)-approximation for maximum weight matching in the semi-streaming model
- A \((2 + \epsilon)\)-approximation for maximum weight matching in the semi-streaming model
Cites work
- A \((2 + \epsilon)\)-approximation for maximum weight matching in the semi-streaming model
- Approximating matching size from random streams
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Better bounds for matchings in the streaming model
- Bipartite matching in the semi-streaming model
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Deterministic fully dynamic data structures for vertex cover and matching
- Faster fully dynamic matchings with small approximation ratios
- Fully dynamic approximate maximum matching and minimum vertex cover in O(^3 n) worst case update time
- scientific article; zbMATH DE number 7053293 (Why is no real title available?)
- Improved approximation guarantees for weighted matching in the semi-streaming model
- Improved bounds for online preemptive matching
- Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
- Linear programming in the semi-streaming model with application to the maximum matching problem
- Maximum matching in semi-streaming with few passes
- Maximum matching in turnstile streams
- Maximum matching in two, three, and a few more passes over graph streams
- Maximum matchings in dynamic graph streams and the simultaneous communication model
- On estimating maximum matching size in graph streams
- On graph problems in a semi-streaming model
- On randomized algorithms for matching in the online preemptive model
- Online algorithms for maximum cardinality matching with edge arrivals
- Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
- Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
- Streaming algorithms for submodular function maximization
- Sublinear estimation of weighted matchings in dynamic data streams
- Weighted matching in the semi-streaming model
Cited in
(10)- Linear programming in the semi-streaming model with application to the maximum matching problem
- Markovian online matching algorithms on large bipartite random graphs
- Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
- Approximate Maximum Matching in Random Streams
- Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
- Parameterized Streaming: Maximal Matching and Vertex Cover
- Constructing large matchings via query access to a maximal matching oracle
- A simple (1-)-approximation semi-streaming algorithm for maximum (weighted) matching
- Weighted matching in the random-order streaming and robust communication models
- Title not available (Why is no real title available?)
This page was built for publication: Deterministic algorithms for maximum matching on general graphs in the semi-streaming model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090980)
