Fixed parameter tractability of graph deletion problems over data streams
From MaRDI portal
Publication:2019516
DOI10.1007/978-3-030-58150-3_53OpenAlexW3081687943MaRDI QIDQ2019516FDOQ2019516
Authors: Arijit Bishnu, Arijit Ghosh, Sudeshna Kolay, Gopinath Mishra, Saket Saurabh 
Publication date: 21 April 2021
Full work available at URL: https://doi.org/10.1007/978-3-030-58150-3_53
Cites Work
- Parameterized algorithms
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Streaming kernelization
- Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
- Parameterized Streaming: Maximal Matching and Vertex Cover
- Structural results on matching estimation with applications to streaming
- Planar matching in streams revisited
- The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
- A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs
- Fixed parameter tractability of graph deletion problems over data streams
- \((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space
- Streaming algorithms for estimating the matching size in planar graphs and beyond
- Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
- Independent sets in vertex-arrival streams
- Tight bounds for single-pass streaming complexity of the set cover problem
- Towards a theory of parameterized streaming algorithms
Cited In (4)
This page was built for publication: Fixed parameter tractability of graph deletion problems over data streams
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2019516)
