Vertex deletion into bipartite permutation graphs

DOI10.1007/S00453-021-00923-7MaRDI QIDQ2161007zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

partially ordered setpermutation graphsgraph modification problemscomparability graphs

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(3)

• A polynomial kernel for bipartite permutation vertex deletion
• Modification problems toward proper (Helly) circular-arc graphs
• 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)