A polynomial kernel for bipartite permutation vertex deletion
type: Item
instance of: scholarly article
title: A polynomial kernel for bipartite permutation vertex deletion
author: Jan Derbisz
author: Lawqueen Kanesh
author: Jayakrishnan Madathil
author: Abhishek Sahu
author: Saket Saurabh
author: Shaily Verma
published in: Algorithmica
publication date: 2022-10-27T00:00:00Z
Mathematics Subject Classification ID: 68Q27
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 7608290
zbMATH Keywords: kernelization
zbMATH Keywords: bipartite permutation graph
zbMATH Keywords: bicliques
MaRDI profile type: Publication
full work available at URL: s00453-022-01040-9
OpenAlex ID: W3215419002
cites work: Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
cites work: Interval Vertex Deletion Admits a Polynomial Kernel
cites work: On problems without polynomial kernels
cites work: Vertex deletion into bipartite permutation graphs
cites work: Graph Classes: A Survey
cites work: Parameterized Algorithms
cites work: Q5743378
cites work: Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
cites work: Fundamentals of parameterized complexity
cites work: New Limits to Classical and Quantum Instance Compression
cites work: Parametrized complexity theory.
cites work: A Polynomial Kernel for Proper Interval Vertex Deletion
cites work: Infeasibility of instance compression and succinct PCPs for NP
cites work: A unified approximation algorithm for node-deletion problems
cites work: Q3328583
cites work: A completeness theory for polynomial (Turing) kernelization
cites work: Q5743381
cites work: Approximation and Kernelization for Chordal Vertex Deletion
cites work: Unit interval vertex deletion: fewer vertices are relevant
cites work: Q4967164
cites work: The node-deletion problem for hereditary properties is NP-complete
cites work: Kernelization – Preprocessing with a Guarantee
cites work: On the hardness of approximating minimization problems
cites work: Chordal deletion is fixed-parameter tractable
cites work: Modular decomposition and transitive orientation
cites work: Q5710169
cites work: Bipartite permutation graphs
cites work: Linear structure of bipartite permutation graphs and the longest path problem
cites work: Node-and edge-deletion NP-complete problems
DOI: 10.1007/S00453-022-01040-9
Recommended article: A polynomial kernel for distance-hereditary vertex deletion
Recommended article: A Polynomial Kernel for Proper Interval Vertex Deletion
Recommended article: Q5363781
Recommended article: A polynomial kernel for block graph deletion
Recommended article: Polynomial Kernel for Interval Vertex Deletion
Recommended article: Polynomial Kernels for Deletion to Classes of Acyclic Digraphs
Recommended article: Polynomial kernels for deletion to classes of acyclic digraphs
Recommended article: Vertex deletion into bipartite permutation graphs
description: scientific article; zbMATH DE number 7608290