Planar Matching in Streams Revisited
From MaRDI portal
Publication:4636449
DOI10.4230/LIPICS.APPROX-RANDOM.2016.17zbMath1398.68682OpenAlexW2555191299MaRDI QIDQ4636449
Sofya Vorotnikova, Andrew McGregor
Publication date: 19 April 2018
Full work available at URL: http://drops.dagstuhl.de/opus/volltexte/2016/6640/
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)
Related Items (10)
Graph sketching and streaming: new approaches for analyzing massive graphs ⋮ Unnamed Item ⋮ 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 ⋮ Structural results on matching estimation with applications to streaming ⋮ Fixed parameter tractability of graph deletion problems over data streams ⋮ (Noisy) gap cycle counting strikes back: random order streaming lower bounds for connected components and beyond ⋮ The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs ⋮ Almost-smooth histograms and sliding-window graph algorithms ⋮ An estimator for matching size in low arboricity graphs with two applications
This page was built for publication: Planar Matching in Streams Revisited
