Fixed parameter tractability of graph deletion problems over data streams

DOI10.1007/978-3-030-58150-3_53OpenAlexW3081687943MaRDI QIDQ2019516

Sudeshna Kolay, Arijit Bishnu, Gopinath Mishra, Saket Saurabh, Arijit Ghosh

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)

Related Items (3)

Streaming deletion problems parameterized by vertex cover ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Fixed parameter tractability of graph deletion problems over data streams

Cites Work

• Unnamed Item
• Unnamed Item
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Structural results on matching estimation with applications to streaming
• Fixed parameter tractability of graph deletion problems over data streams
• Streaming Kernelization
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• (1 + Ω(1))-Αpproximation to MAX-CUT Requires Linear Space
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• Planar Matching in Streams Revisited
• Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph
• The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs
• Tight bounds for single-pass streaming complexity of the set cover problem
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Parameterized Algorithms
• Towards a theory of parameterized streaming algorithms

This page was built for publication: Fixed parameter tractability of graph deletion problems over data streams