Vertex deletion into bipartite permutation graphs

DOI10.1007/s00453-021-00923-7OpenAlexW4210418612MaRDI QIDQ2161007

Tomasz Krawczyk, Jan Derbisz, Jana Novotná, Łukasz Bożyk, 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

zbMATH Keywords

partially ordered setcomparability graphspermutation graphsgraph modification problems

Mathematics Subject Classification ID

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

Cites Work

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

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