Fixed parameter tractability of graph deletion problems over data streams

DOI10.1007/978-3-030-58150-3_53MaRDI QIDQ2019516zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• A simple, space-efficient, streaming algorithm for matchings in low arboricity graphs
• Fixed parameter tractability of graph deletion problems over data streams
• Independent sets in vertex-arrival streams
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Parameterized algorithms
• Planar matching in streams revisited
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Streaming algorithms for estimating the matching size in planar graphs and beyond
• Streaming complexity of approximating Max 2CSP and Max Acyclic Subgraph
• Streaming kernelization
• Structural results on matching estimation with applications to streaming
• The sparse awakens: streaming algorithms for matching size estimation in sparse graphs
• Tight bounds for single-pass streaming complexity of the set cover problem
• Towards a theory of parameterized streaming algorithms
• \((1 + \Omega(1))\)-approximation to MAX-CUT requires linear space

Cited in

(4)

• Streaming deletion problems parameterized by vertex cover
• Parameterized complexity of streaming diameter and connectivity problems
• Streaming deletion problems Parameterized by vertex cover
• Fixed parameter tractability of graph deletion problems over data streams

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)