Quadratic vertex kernel for split vertex deletion
DOI10.1016/j.tcs.2020.06.001zbMath1451.68196OpenAlexW3033871064MaRDI QIDQ5896158
Pallavi Jain, Akanksha Agrawal, Sushmita Gupta, R. Krithika
Publication date: 3 August 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2020.06.001
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- Parameterized complexity of vertex deletion into perfect graph classes
- Chordal deletion is fixed-parameter tractable
- A kernelization algorithm for \(d\)-hitting set
- The node-deletion problem for hereditary properties is NP-complete
- Yet another method of enumerating unmarked combinatorial objects
- A unified approximation algorithm for node-deletion problems
- Fixed-parameter tractability of graph modification problems for hereditary properties
- \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
- Faster parameterized algorithms for deletion to split graphs
- Obtaining a planar graph by vertex deletion
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- On the hardness of approximating minimization problems
- Approximation and Kernelization for Chordal Vertex Deletion
- Kernelization
- Faster Parameterized Algorithms Using Linear Programming
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Subexponential Parameterized Algorithm for Minimum Fill-In
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
This page was built for publication: Quadratic vertex kernel for split vertex deletion
