Quadratic vertex kernel for split vertex deletion
From MaRDI portal
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) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
- Quadratic vertex kernel for split vertex deletion
- A quartic kernel for pathwidth-one vertex deletion
- Polynomial Kernel for Interval Vertex Deletion
- A Polynomial Kernel for Proper Interval Vertex Deletion
- Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
- A quadratic kernel for feedback vertex set
- Approximation and kernelization for chordal vertex deletion
- Approximation and kernelization for chordal vertex deletion
- A polynomial kernel for distance-hereditary vertex deletion
- A polynomial kernel for distance-hereditary vertex deletion
Cites work
- \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
- A kernelization algorithm for \(d\)-hitting set
- A unified approximation algorithm for node-deletion problems
- Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization
- Approximation and kernelization for chordal vertex deletion
- Chordal deletion is fixed-parameter tractable
- Faster parameterized algorithms for deletion to split graphs
- Faster parameterized algorithms using linear programming
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Graph theory
- scientific article; zbMATH DE number 3632548 (Why is no real title available?)
- Kernelization. Theory of parameterized preprocessing
- Obtaining a planar graph by vertex deletion
- On the hardness of approximating minimization problems
- Parameterized algorithms
- Parameterized complexity of vertex deletion into perfect graph classes
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Subexponential parameterized algorithm for minimum fill-in
- The node-deletion problem for hereditary properties is NP-complete
- Yet another method of enumerating unmarked combinatorial objects
Cited in
(14)- \textsc{Split Vertex Deletion} meets \textsc{Vertex Cover}: new fixed-parameter and exact exponential-time algorithms
- Faster parameterized algorithms for deletion to split graphs
- On the kernelization of split graph problems
- Algorithms for deletion problems on split graphs
- Faster parameterized algorithms for deletion to split graphs
- König Deletion Sets and Vertex Covers above the Matching Size
- Kernelization of two path searching problems on split graphs
- How to eliminate a graph
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Vertex deletion on split graphs: beyond 4-hitting set
- Quadratic vertex kernel for split vertex deletion
- Polynomial Kernel for Interval Vertex Deletion
- A simple \((2 + \epsilon)\)-approximation algorithm for split vertex deletion
- Bisplit graphs -- a structural and algorithmic study
This page was built for publication: Quadratic vertex kernel for split vertex deletion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5896158)
