Polynomial Kernel for Interval Vertex Deletion
From MaRDI portal
Publication:6075746
DOI10.1145/3571075MaRDI QIDQ6075746
Daniel Lokshtanov, Meirav Zehavi, Saket Saurabh, Akanksha Agrawal, Pranabendu Misra
Publication date: 23 October 2023
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Chordal editing is fixed-parameter tractable
- Fundamentals of parameterized complexity
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Unit interval editing is fixed-parameter tractable
- Infeasibility of instance compression and succinct PCPs for NP
- Chordal deletion is fixed-parameter tractable
- On problems without polynomial kernels
- A parameterized view on matroid optimization problems
- The node-deletion problem for hereditary properties is NP-complete
- A unified approximation algorithm for node-deletion problems
- Unit interval vertex deletion: fewer vertices are relevant
- A completeness theory for polynomial (Turing) kernelization
- Incidence matrices and interval graphs
- A polynomial kernel for block graph deletion
- Parametrized complexity theory.
- Incidence matrices, interval graphs and seriation in archeology
- A characterization of perfect graphs
- A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
- Kernelization – Preprocessing with a Guarantee
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- Representation of a finite graph by a set of intervals on the real line
- New Limits to Classical and Quantum Instance Compression
- Graph Classes: A Survey
- On the hardness of approximating minimization problems
- Linear Recognition of Almost Interval Graphs
- Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
- Approximation and Kernelization for Chordal Vertex Deletion
- Approximation and Kernelization for Chordal Vertex Deletion
- Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
- Interval Deletion Is Fixed-Parameter Tractable
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- Simultaneous Feedback Vertex Set
- A Near-Optimal Planarization Algorithm
- Node-and edge-deletion NP-complete problems
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- On generalized graphs
- A unified approach to approximating resource allocation and scheduling
This page was built for publication: Polynomial Kernel for Interval Vertex Deletion
