A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs
Andrew McGregor, Sofya Vorotnikova · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2018
We present a simple single-pass data stream algorithm using O((log n)/eps^2) space that returns an (alpha + 2)(1 + eps) approximation to the size of the maximum matching in a graph of arboricity alpha.