Towards a theory of parameterized streaming algorithms

DOI10.4230/LIPICS.IPEC.2019.7MaRDI QIDQ5875539zbMATH OpenOpenAlexFDO

Authors Rajesh Chitnis, Graham Cormode

Publication date 3 February 2023

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

zbMATH Keywords

kernelsparameterized algorithmsstreaming algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cited in

(13)

• Fixed parameter tractability of graph deletion problems over data streams
• Linear-time parameterized algorithms with limited local resources
• Streaming deletion problems parameterized by vertex cover
• Characterizing polynomial time complexity of stream programs using interpretations
• Streaming Algorithms Measured in Terms of the Computed Quantity
• Streaming deletion problems Parameterized by vertex cover
• FPT-Algorithms for the \(\ell\) -Matchoid Problem with a Coverage Objective
• Nearly time-optimal kernelization algorithms for the line-cover problem with big data
• Maximum unique coverage on streams: improved FPT approximation scheme and tighter space lower bound
• Parameterized complexity of streaming diameter and connectivity problems
• Maximum coverage in the data stream model: parameterized and generalized
• Parameterized quantum query algorithms for graph problems
• Parameterized streaming algorithms for topological sorting

This page was built for publication: Towards a theory of parameterized streaming algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875539)