On Estimating Maximum Matching Size in Graph Streams

DOI10.1137/1.9781611974782.113zbMath1409.68336arXiv1701.04364OpenAlexW2949572027MaRDI QIDQ4575856

Sanjeev Khanna, Yang Li, Sepehr Assadi

Publication date: 16 July 2018

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items

Graph sketching and streaming: new approaches for analyzing massive graphs ⋮ Maximum matchings and minimum dominating sets in Apollonian networks and extended tower of Hanoi graphs ⋮ Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ Structural results on matching estimation with applications to streaming ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Querying a Matrix Through Matrix-Vector Products. ⋮ Optimality of linear sketching under modular updates ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs ⋮ On Approximating Matrix Norms in Data Streams