Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond

DOI10.1137/1.9781611973730.81zbMath1371.68329OpenAlexW4239886656MaRDI QIDQ5363103

Vahid Liaghat, Hossein Esfandiari, Krzysztof Onak, Morteza Monemizadeh, Mohammad Taghi Hajiaghayi

Publication date: 5 October 2017

Published in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973730.81

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Online algorithms; streaming algorithms (68W27)

Related Items (13)

Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ Maximum Matching in Turnstile Streams ⋮ Unnamed Item ⋮ Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs ⋮ A Hall-type theorem with algorithmic consequences in planar graphs ⋮ Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams ⋮ Brief Announcement: MapReduce Algorithms for Massive Trees ⋮ A simple augmentation method for matchings with applications to streaming algorithms ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Structural results on matching estimation with applications to streaming ⋮ Unnamed Item ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs ⋮ An estimator for matching size in low arboricity graphs with two applications

This page was built for publication: Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond