Bipartite matching in the semi-streaming model

DOI10.1007/s00453-011-9556-8zbMath1236.68295OpenAlexW2157523155MaRDI QIDQ2429353

Peter Munstermann, Anand Srivastav, Lasse Kliemann, Sebastian Eggert

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://macau.uni-kiel.de/receive/macau_mods_00001819

zbMATH Keywords

approximation schemesapproximation algorithmsstreaming algorithmsbipartite graph matching

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Maximum Matching in Turnstile Streams ⋮ Superlinear lower bounds for multipass graph processing ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ On conceptually simple algorithms for variants of online bipartite matching ⋮ Unnamed Item ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs

Cites Work

• TWO THEOREMS IN GRAPH THEORY
• Data Streams: Algorithms and Applications
• Bipartite Graph Matchings in the Semi-streaming Model
• Algorithms – ESA 2004
• Automata, Languages and Programming
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs