Parameterized Streaming: Maximal Matching and Vertex Cover

DOI10.1137/1.9781611973730.82zbMath1372.68207OpenAlexW4229914019MaRDI QIDQ5363104

Rajesh Chitnis, Morteza Monemizadeh, Graham Cormode, 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.82

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items (13)

Streaming deletion problems parameterized by vertex cover ⋮ Parameterized analysis and crossing minimization problems ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective ⋮ Space limited graph algorithms on big data ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ Space limited linear-time graph algorithms on big data ⋮ Brief Announcement: MapReduce Algorithms for Massive Trees ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Fixed parameter tractability of graph deletion problems over data streams ⋮ Optimality of linear sketching under modular updates ⋮ Linear-time parameterized algorithms with limited local resources ⋮ An estimator for matching size in low arboricity graphs with two applications

This page was built for publication: Parameterized Streaming: Maximal Matching and Vertex Cover