A Note on Logarithmic Space Stream Algorithms for Matchings in Low Arboricity Graphs

Andrew McGregor, Sofya Vorotnikova

We present a data stream algorithm for estimating the size of the maximum matching of a low arboricity graph. Recall that a graph has arboricity $\alpha$ if its edges can be partitioned…