Deterministic algorithms for maximum matching on general graphs in the semi-streaming model

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

scientific article; zbMATH DE number 7053293 (Why is no real title available?)
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(\log^3 n)\) worst case update time
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

(6)

Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
Markovian online matching algorithms on large bipartite random graphs
Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
Approximate Maximum Matching in Random Streams
Linear programming in the semi-streaming model with application to the maximum matching problem
Parameterized Streaming: Maximal Matching and Vertex Cover

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)