Polynomial Kernel for Interval Vertex Deletion
From MaRDI portal
Recommendations
- A Polynomial Kernel for Proper Interval Vertex Deletion
- Interval vertex deletion admits a polynomial kernel
- A polynomial kernel for \textsc{Proper Interval Vertex Deletion}
- A polynomial kernel for distance-hereditary vertex deletion
- A polynomial kernel for distance-hereditary vertex deletion
- A Polynomial Kernel for Line Graph Deletion
- A polynomial kernel for block graph deletion
- A polynomial kernel for block graph deletion
- A polynomial kernel for bipartite permutation vertex deletion
- Quadratic vertex kernel for split vertex deletion
Cites work
- A characterization of perfect graphs
- A completeness theory for polynomial (Turing) kernelization
- A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
- A near-optimal planarization algorithm
- A parameterized view on matroid optimization problems
- A polynomial kernel for block graph deletion
- A unified approach to approximating resource allocation and scheduling
- A unified approximation algorithm for node-deletion problems
- Approximation and kernelization for chordal vertex deletion
- Approximation and kernelization for chordal vertex deletion
- Chordal deletion is fixed-parameter tractable
- Chordal editing is fixed-parameter tractable
- Efficient computation of representative families with applications in parameterized and exact algorithms
- Feedback vertex set inspired kernel for chordal vertex deletion
- Feedback vertex set inspired kernel for chordal vertex deletion
- Fundamentals of parameterized complexity
- Graph Classes: A Survey
- Graph theory
- scientific article; zbMATH DE number 3859178 (Why is no real title available?)
- scientific article; zbMATH DE number 5047784 (Why is no real title available?)
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- Incidence matrices and interval graphs
- Incidence matrices, interval graphs and seriation in archeology
- Infeasibility of instance compression and succinct PCPs for NP
- Interval deletion is fixed-parameter tractable
- Kernelization -- preprocessing with a guarantee
- Kernelization of packing problems
- Linear recognition of almost interval graphs
- New limits to classical and quantum instance compression
- Node-and edge-deletion NP-complete problems
- On generalized graphs
- On problems without polynomial kernels
- On the hardness of approximating minimization problems
- Parameterized algorithms
- Parametrized complexity theory.
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Recent developments in kernelization: a survey
- Representation of a finite graph by a set of intervals on the real line
- Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
- Simultaneous feedback vertex set: a parameterized perspective
- The node-deletion problem for hereditary properties is NP-complete
- Unit interval vertex deletion: fewer vertices are relevant
Cited in
(8)- A polynomial kernel for bipartite permutation vertex deletion
- Polynomial kernelization for removing induced claws and diamonds
- A polynomial kernel for block graph deletion
- Proper Interval Vertex Deletion
- A Polynomial Kernel for Proper Interval Vertex Deletion
- Quadratic vertex kernel for split vertex deletion
- A polynomial kernel for distance-hereditary vertex deletion
- Approximate Turing kernelization for problems parameterized by treewidth
This page was built for publication: Polynomial Kernel for Interval Vertex Deletion
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6075746)
