Streaming deletion problems Parameterized by vertex cover

DOI10.1016/J.TCS.2023.114178MaRDI QIDQ6057830zbMATH OpenOpenAlexFDO

Authors Jelle J. Oostveen, Erik Jan van Leeuwen

Publication date 26 October 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.tcs.2023.114178

zbMATH Keywords

graph streamingparameterized complexityvertex coververtex deletion

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Linear Recognition Algorithm for Cographs
• A simple linear-time algorithm for computing the center of an interval graph
• Counting and detecting small subgraphs via equations
• Data streams: algorithms and applications.
• Faster parameterized algorithm for cluster vertex deletion
• Finding a Minimum Circuit in a Graph
• Finding and counting small induced subgraphs efficiently
• Finding four-node subgraphs in triangle time
• Finding odd cycle transversals.
• Fixed parameter tractability of graph deletion problems over data streams
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graph distances in the streaming model: the value of space
• Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
• Graph pattern polynomials
• Hitting forbidden induced subgraphs on bounded treewidth graphs
• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• scientific article; zbMATH DE number 1424324 (Why is no real title available?)
• scientific article; zbMATH DE number 7650305 (Why is no real title available?)
• Independent sets in vertex-arrival streams
• Kernelization Lower Bounds by Cross-Composition
• Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
• Maximum common induced subgraph parameterized by vertex cover
• On graph problems in a semi-streaming model
• On the complexity of k-SAT
• On the complexity of fixed parameter clique and dominating set
• On the parameterized complexity of graph modification to first-order logic properties
• Parameterized algorithms
• Parameterized complexity of finding regular induced subgraphs
• Parameterized Streaming: Maximal Matching and Vertex Cover
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
• Preprocessing subgraph and minor problems: when does a small vertex cover help?
• Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
• Slightly superexponential parameterized problems
• Streaming kernelization
• Subgraph isomorphism in graph classes
• The node-deletion problem for hereditary properties is NP-complete
• Towards a theory of parameterized streaming algorithms

Cited in

(2)

• Parameterized Streaming: Maximal Matching and Vertex Cover
• Nearly-tight bounds for flow sparsifiers in quasi-bipartite graphs

This page was built for publication: Streaming deletion problems Parameterized by vertex cover

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