Approximating matching size from random streams

DOI10.1137/1.9781611973402.55zbMath1423.68344OpenAlexW4234540089MaRDI QIDQ5384016

Sanjeev Khanna, Michael Kapralov

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973402.55

Mathematics Subject Classification ID

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

Related Items (14)

Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Unnamed Item ⋮ Round Compression for Parallel Matching Algorithms ⋮ Communication complexity of approximate maximum matching in the message-passing model ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ Sublinear Algorithms for MAXCUT and Correlation Clustering ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Structural results on matching estimation with applications to streaming ⋮ Unnamed Item ⋮ Optimal lower bounds for matching and vertex cover in dynamic graph streams ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs ⋮ Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem ⋮ An estimator for matching size in low arboricity graphs with two applications

This page was built for publication: Approximating matching size from random streams