Approximating matching size from random streams

DOI10.1137/1.9781611973402.55MaRDI QIDQ5384016zbMATH OpenOpenAlexFDO

Authors Michael Kapralov, Sanjeev Khanna, Madhu Sudan

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

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

Recommendations

• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• On estimating maximum matching size in graph streams
• Structural results on matching estimation with applications to streaming
• The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
• A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs

Cited in

(33)

• Dynamic graph stream algorithms in \(o(n)\) space
• Structural results on matching estimation with applications to streaming
• An estimator for matching size in low arboricity graphs with two applications
• Communication complexity of approximate maximum matching in the message-passing model
• Maximum matching in turnstile streams
• On estimating maximum matching size in graph streams
• Estimating graph parameters from random order streams
• Tight bounds for single-pass streaming complexity of the set cover problem
• 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
• Deterministic algorithms for maximum matching on general graphs in the semi-streaming model
• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Testable bounded degree graph properties are random order streamable
• The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
• Round compression for parallel matching algorithms
• Approximate Maximum Matching in Random Streams
• Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs
• A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Better bounds for matchings in the streaming model
• scientific article; zbMATH DE number 7758318 (Why is no real title available?)
• Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model
• (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond
• Delay epidemic models determined by latency, infection, and immunity duration
• Improved bounds for matching in random-order streams
• Improved bounds for matching in random-order streams
• Weighted matching in the random-order streaming and robust communication models
• Dynamics of delay epidemic model with periodic transmission rate
• Sketching approximability of all finite CSPs
• Maximum coverage in the data stream model: parameterized and generalized
• Matchings in low-arboricity graphs in the dynamic graph stream model
• Delay epidemic model with spatial distribution

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384016)