A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs

Authors Andrew McGregor, Sofya Vorotnikova



PDF
Thumbnail PDF

File

OASIcs.SOSA.2018.14.pdf
  • Filesize: 387 kB
  • 4 pages

Document Identifiers

Author Details

Andrew McGregor
Sofya Vorotnikova

Cite AsGet BibTex

Andrew McGregor and Sofya Vorotnikova. A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 14:1-14:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/OASIcs.SOSA.2018.14

Abstract

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.
Keywords
  • data streams
  • matching
  • planar graphs
  • arboricity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail