Maximum Matching in Turnstile Streams

DOI10.1007/978-3-662-48350-3_70zbMath1466.68088arXiv1505.01460OpenAlexW2225286048MaRDI QIDQ3452845

Christian Konrad

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (15)

Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ High Probability Frequency Moment Sketches ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams. ⋮ Structural results on matching estimation with applications to streaming ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On regularity lemma and barriers in streaming and dynamic matching ⋮ Querying a Matrix Through Matrix-Vector Products. ⋮ Optimal lower bounds for matching and vertex cover in dynamic graph streams ⋮ Optimality of linear sketching under modular updates ⋮ Better streaming algorithms for the maximum coverage problem

Cites Work

• Unnamed Item
• Unnamed Item
• Superlinear lower bounds for multipass graph processing
• Weighted matching in the semi-streaming model
• Bipartite matching in the semi-streaming model
• On graph problems in a semi-streaming model
• Dynamic Graphs in the Sliding-Window Model
• Spectral Sparsification in Dynamic Graph Streams
• Spanners and sparsifiers in dynamic streams
• Single Pass Spectral Sparsification in Dynamic Streams
• Linear Programming in the Semi-streaming Model with Application to the Maximum Matching Problem
• IMPROVED APPROXIMATION GUARANTEES FOR WEIGHTED MATCHING IN THE SEMI-STREAMING MODEL *
• Maximum Matching in Semi-streaming with Few Passes
• Turnstile streaming algorithms might as well be linear sketches
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Maximum Matching in Turnstile Streams