2016/12/08 by Andrew McGregor, McGregor, Andrew, Sofya Vorotnikova +1
Computer Science · #Caching and Content Delivery #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1612.02531
openalex publication_date 2016/12/08 · openalex created_date 2022/09/15 · openalex updated_date 2026/07/28
We present a data stream algorithm for estimating the size of the maximum\nmatching of a low arboricity graph. Recall that a graph has arboricity \α\nif its edges can be partitioned into at most \α forests and that a planar\ngraph has arboricity \α=3. Estimating the size of the maximum matching in\nsuch graphs has been a focus of recent data stream research.\n A surprising result on this problem was recently proved by Cormode et al.\nThey designed an ingenious algorithm that returned a\n(22.5\α+6)(1+\ε) approximation using a single pass over the edges\nof the graph (ordered arbitrarily) and O(\ε-2\α \⋅ \log n\n\⋅ \log1+\ε n) space. In this note, we improve the approximation\nfactor to (\α+2)(1+\ε) via a tighter analysis and show that, with a\nmodification of their algorithm, the space required can be reduced to\nO(\ε-2 \log n).\n