G. Cormode, H. Jowhari, M. Monemizadeh, and S. Muthukrishnan. Streaming algorithms for matching size estimation in sparse graphs. In European Symposium on Algorithms, 2017.

Estimating the size of the maximum matching is a canonical problem in graph analysis, and one that has attracted extensive study over a range of different computational models. We present improved streaming algorithms for approximating the size of maximum matching with sparse (bounded arboricity) graphs.

In contrast to prior work, our results take more advantage of the streaming access to the input and characterize the matching size based on the ordering of the edges in the stream in addition to the degree distributions and structural properties of the sparse graphs.

bib | http | slides | .pdf ] Back


This file was generated by bibtex2html 1.92.