Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes
From MaRDI portal
Publication:2232241
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
Related Items (1)
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
