Streaming Kernelization

DOI10.1007/978-3-662-44465-8_24zbMath1426.68120arXiv1405.1356OpenAlexW3037240142MaRDI QIDQ2922615

Stefan Kratsch, Stefan Fafianie

Publication date: 14 October 2014

Published in: Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1405.1356

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Online algorithms; streaming algorithms (68W27)

Related Items (14)

Multistage graph problems on a global budget ⋮ Streaming deletion problems parameterized by vertex cover ⋮ Space-efficient vertex separators for treewidth ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU ⋮ 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 ⋮ Optimal-size problem kernels for \(d\)-Hitting Set in linear time and space ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ Fixed parameter tractability of graph deletion problems over data streams ⋮ Linear-time parameterized algorithms with limited local resources ⋮ A linear-time kernelization for the rooted \(k\)-leaf outbranching problem

This page was built for publication: Streaming Kernelization