13 citations · 35 across the 15 of their papers we have counts for
3 papers · 1 filter
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…
Streaming Weighted Matchings: Optimal Meets Greedy
Elena Grigorescu, Morteza Monemizadeh, Samson Zhou
We consider the problem of approximating a maximum weighted matching, when the edges of an underlying weighted graph are revealed in a streaming fashion. We analyze a vari…
Estimating Weighted Matchings in Space
Elena Grigorescu, Morteza Monemizadeh, Samson Zhou
We consider the problem of estimating the weight of a maximum weighted matching of a weighted graph whose edges are revealed in a streaming fashion. We develop a reduction…