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

DOI10.1145/3230819zbMath1454.68191OpenAlexW2889287172MaRDI QIDQ4629961

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

Publication date: 28 March 2019

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3230819

zbMATH Keywords

planar graphsmaximal matchingstreaming algorithmsbounded arboricityestimating matching size

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 (6)

Maximum matching sans maximal matching: a new approach for finding maximum matchings in the data stream model ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ Unnamed Item ⋮ Fixed parameter tractability of graph deletion problems over data streams ⋮ Almost-smooth histograms and sliding-window graph algorithms ⋮ Linear-time parameterized algorithms with limited local resources

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