A polynomial kernel for bipartite permutation vertex deletion
From MaRDI portal
Publication:2093571
DOI10.1007/s00453-022-01040-9OpenAlexW3215419002MaRDI QIDQ2093571
Jayakrishnan Madathil, Lawqueen Kanesh, Saket Saurabh, Abhishek Sahu, Shaily Verma, Jan Derbisz
Publication date: 27 October 2022
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-022-01040-9
Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Infeasibility of instance compression and succinct PCPs for NP
- Chordal deletion is fixed-parameter tractable
- On problems without polynomial kernels
- Bipartite permutation graphs
- The node-deletion problem for hereditary properties is NP-complete
- A unified approximation algorithm for node-deletion problems
- Modular decomposition and transitive orientation
- Unit interval vertex deletion: fewer vertices are relevant
- A completeness theory for polynomial (Turing) kernelization
- Linear structure of bipartite permutation graphs and the longest path problem
- Parametrized complexity theory.
- Kernelization – Preprocessing with a Guarantee
- New Limits to Classical and Quantum Instance Compression
- Graph Classes: A Survey
- On the hardness of approximating minimization problems
- Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
- Approximation and Kernelization for Chordal Vertex Deletion
- Interval Vertex Deletion Admits a Polynomial Kernel
- Node-and edge-deletion NP-complete problems
- A Polynomial Kernel for Proper Interval Vertex Deletion
- Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
- Parameterized Algorithms
- Vertex deletion into bipartite permutation graphs
This page was built for publication: A polynomial kernel for bipartite permutation vertex deletion
