## G. Cormode, H. Jowhari, M. Monemizadeh, and S. Muthukrishnan.
The sparse awakens: Streaming algorithms for matching size estimation
in sparse graphs.
Technical report, ArXiV, 2016.

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.
We present improved streaming algorithms for approximating the size of maximum matching with sparse (bounded arboricity) graphs.
* *(Insert-Only Streams)*
We present a one-pass algorithm that takes *O*(*c*log^{2} *n*) space and approximates the size of the maximum matching in
graphs with arboricity *c* within a factor of *O*(*c*). This improves significantly upon the state-of-the-art *O*~(*cn*^{2/3})-space streaming algorithms.
* *(Dynamic Streams)*
Given a dynamic graph stream (i.e., inserts and deletes) of edges of an underlying *c*-bounded arboricity graph,
we present an one-pass algorithm that uses space *O*(*c*^{10/3}*n*^{2/3})
and returns an *O*(*c*)-estimator for the size of the maximum matching.
This algorithm improves the state-of-the-art *O*~(*cn*^{4/5})-space algorithms, where the *O*~(.) notation hides logarithmic in *n* dependencies.
* *(Random Order Streams)*
For randomly ordered graph streams, we present a two-pass streaming algorithm
that outputs a (1+ε)-approximation of the maximal matching size using *O*(*d*^{d^d+6}) space
for graphs with maximum degree bounded by *d*. The previous best algorithm for this setting is an *O*(log*d*) approximation.
Our algorithm is the first with an approximation guarantee independent
of *d*. Our result is obtained by simulating a property-testing result
in a streaming setting, a technique which might be of independent interest.
In contrast to the previous works, 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 |
Alternate Version ]
Back

*This file was generated by
bibtex2html 1.92.*