Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams

DOI10.4230/LIPIcs.APPROX-RANDOM.2017.15zbMath1467.68224arXiv1702.02559OpenAlexW2962933030MaRDI QIDQ5002618

Sumedh Tirodkar, Sagar Kale

Publication date: 28 July 2021

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

zbMATH Keywords

maximum matchingsemi-streaming

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items

Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Improved bounds for randomized preemptive online matching ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ Unnamed Item ⋮ Depth First Search in the Semi-streaming Model ⋮ Optimal lower bounds for matching and vertex cover in dynamic graph streams ⋮ Multi-pass streaming algorithms for monotone submodular function maximization

Cites Work

• Unnamed Item
• Unnamed Item
• Submodular maximization meets streaming: matchings, matroids, and more
• Linear programming in the semi-streaming model with application to the maximum matching problem
• Bipartite matching in the semi-streaming model
• On graph problems in a semi-streaming model
• Maximum Matching in Semi-streaming with Few Passes
• Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
• Streaming Algorithms for Submodular Function Maximization
• 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
• On Estimating Maximum Matching Size in Graph Streams
• A (2 + ∊)-Approximation for Maximum Weight Matching in the Semi-Streaming Model
• Weighted Matching in the Semi-Streaming Model
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• Approximating matching size from random streams
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Better bounds for matchings in the streaming model

This page was built for publication: Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams