Vertex deletion into bipartite permutation graphs

DOI10.1007/S00453-021-00923-7OpenAlexW4210418612MaRDI QIDQ2161007FDOQ2161007

Authors: Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotná, Karolina Okrasa 

Publication date: 3 August 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2010.11440

Recommendations

• Vertex deletion into bipartite permutation graphs
• A polynomial kernel for bipartite permutation vertex deletion
• A polynomial kernel for bipartite permutation vertex deletion
• scientific article; zbMATH DE number 3919840
• Bipartite permutation graphs

zbMATH Keywords

partially ordered setpermutation graphsgraph modification problemscomparability graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Geometric algorithms and combinatorial optimization
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
• The node-deletion problem for hereditary properties is NP-complete
• Comparability graphs and intersection graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• The strong perfect graph theorem
• Representation of a finite graph by a set of intervals on the real line
• Transitiv orientierbare Graphen
• Bipartite permutation graphs
• Characterization problems for graphs, partially ordered sets, lattices, and families of sets
• The 3-Irreducible Partially Ordered Sets
• Partial orders of dimension 2
• Chordal editing is fixed-parameter tractable
• Chordal deletion is fixed-parameter tractable
• Interval Completion Is Fixed Parameter Tractable
• Title not available (Why is that?)
• Parameterized complexity of vertex deletion into perfect graph classes
• Proper interval vertex deletion
• Linear recognition of almost interval graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• Wheel-Free Deletion Is W[2]-Hard
• Computing the cutwidth of bipartite permutation graphs in linear time
• Vertex deletion into bipartite permutation graphs

Cited In (3)

• Modification problems toward proper (Helly) circular-arc graphs
• A polynomial kernel for bipartite permutation vertex deletion
• Vertex deletion into bipartite permutation graphs

This page was built for publication: Vertex deletion into bipartite permutation graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2161007)