The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs

Graham Cormode, Hossein Jowhari, Morteza Monemizadeh +1

Estimating the size of the maximum matching is a canonical problem in graph algorithms, and one that has attracted extensive study over a range of different computational models. W…