Maximum Matching in Semi-streaming with Few Passes

DOI10.1007/978-3-642-32512-0_20zbMath1372.68311arXiv1112.0184OpenAlexW1871809785MaRDI QIDQ3167399

Claire Mathieu, Frédéric Magniez, Christian Konrad

Publication date: 2 November 2012

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.0184

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (17)

Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ Maximum Matching in Turnstile Streams ⋮ Superlinear lower bounds for multipass graph processing ⋮ Graph sketching and streaming: new approaches for analyzing massive graphs ⋮ Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Unnamed Item ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ Structural results on matching estimation with applications to streaming ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Unnamed Item ⋮ On regularity lemma and barriers in streaming and dynamic matching ⋮ Improved bounds for matching in random-order streams ⋮ Online submodular maximization: beating 1/2 made simple ⋮ Optimal lower bounds for matching and vertex cover in dynamic graph streams ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs

This page was built for publication: Maximum Matching in Semi-streaming with Few Passes