Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes

DOI10.1007/978-3-030-68211-8_12OpenAlexW3135607492MaRDI QIDQ2232241

Ryo Yoshinaka, Toshiki Saitoh, Hans L. Bodlaender

Publication date: 4 October 2021

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

zbMATH Keywords

treewidthinterval graphsparameterized algorithmsedge-deletion

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (1)

Edge deletion to tree-like graph classes

Cites Work

• Unnamed Item
• Parameterized complexity of vertex deletion into perfect graph classes
• Polynomial kernels for proper interval completion and related problems
• Chordal deletion is fixed-parameter tractable
• Interval graphs and maps of DNA
• The node-deletion problem for hereditary properties is NP-complete
• Some complexity results about threshold graphs
• Treewidth. Computations and approximations
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Efficient graph representations
• A polynomial kernel for trivially perfect editing
• Algorithmic graph theory and perfect graphs
• Proper interval vertex deletion
• Edge deletion problems: branching facilitated by modular decomposition
• The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
• NP-completeness results for edge modification problems
• BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES
• Interval Completion Is Fixed Parameter Tractable
• Graph Classes: A Survey
• Linear Recognition of Almost Interval Graphs
• Interval Deletion Is Fixed-Parameter Tractable
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Complexity classification of some edge modification problems

This page was built for publication: Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes