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

DOI10.4230/LIPICS.FSTTCS.2018.39MaRDI QIDQ5090980FDOQ5090980

Publication date: 21 July 2022

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

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites Work

Combinatorial optimization. Polyhedra and efficiency (3 volumes)
Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
On graph problems in a semi-streaming model
Improved approximation guarantees for weighted matching in the semi-streaming model
Bipartite matching in the semi-streaming model
Maximum matching in semi-streaming with few passes
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Better bounds for matchings in the streaming model
Title not available (Why is that?)
On randomized algorithms for matching in the online preemptive model
Improved bounds for online preemptive matching
Online algorithms for maximum cardinality matching with edge arrivals
Submodular maximization meets streaming: matchings, matroids, and more
Streaming algorithms for submodular function maximization
Weighted matching in the semi-streaming model
Deterministic fully dynamic data structures for vertex cover and matching
On estimating maximum matching size in graph streams
Linear programming in the semi-streaming model with application to the maximum matching problem
A \((2 + \epsilon)\)-approximation for maximum weight matching in the semi-streaming model
Maximum matching in two, three, and a few more passes over graph streams
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
Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
Approximating matching size from random streams
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

Cited In (6)

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

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)