The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs

DOI10.4230/LIPIcs.ESA.2017.29zbMath1442.68273arXiv1608.03118OpenAlexW2963373149MaRDI QIDQ5111716

No author found.

Publication date: 27 May 2020

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

zbMATH Keywords

streaming algorithmsmatching size

Mathematics Subject Classification ID

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

Related Items (10)

Unnamed Item ⋮ Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ Unnamed Item ⋮ Structural results on matching estimation with applications to streaming ⋮ Fixed parameter tractability of graph deletion problems over data streams ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs ⋮ Almost-smooth histograms and sliding-window graph algorithms ⋮ An estimator for matching size in low arboricity graphs with two applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bound of the Hadwiger number of graphs by their average degree
• Matching theory
• Weighted matching in the semi-streaming model
• Bipartite matching in the semi-streaming model
• On graph problems in a semi-streaming model
• Spectral Sparsification in Dynamic Graph Streams
• Maximum Matching in Semi-streaming with Few Passes
• Linear-Time Approximation for Maximum Weight Matching
• Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
• Edge-Disjoint Spanning Trees of Finite Graphs
• Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
• Matching for Graphs of Bounded Degree
• AdWords and generalized online matching
• 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
• Planar Matching in Streams Revisited
• The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs
• On Unifying the Space of ℓ₀-Sampling Algorithms
• 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
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Decomposition of Finite Graphs Into Forests
• Better bounds for matchings in the streaming model

This page was built for publication: The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs