A cubic vertex-kernel for \textsc{Trivially Perfect Editing}
From MaRDI portal
Publication:2696282
DOI10.1007/s00453-022-01070-3OpenAlexW3161835050MaRDI QIDQ2696282
Ioan Todinca, Maël Dumas, Anthony Perez
Publication date: 11 April 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2105.08549
Cites Work
- Chordal editing is fixed-parameter tractable
- Polynomial kernels for proper interval completion and related problems
- Polynomial kernels for 3-leaf power graph modification problems
- On low tree-depth decompositions
- Trivially perfect graphs
- On the complexity of DNA physical mapping
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Two edge modification problems without polynomial kernels
- A polynomial kernel for trivially perfect editing
- Quasi-threshold graphs
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
- Applying modular decomposition to parameterized cluster editing problems
- Incompressibility of \(H\)-free edge modification problems
- Faster parameterized algorithms for deletion to split graphs
- NP-completeness results for edge modification problems
- A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
- Exploring the Subexponential Complexity of Completion Problems
- The complexity of some edge deletion problems
- Computing the Minimum Fill-In is NP-Complete
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Kernelization
- Dichotomy Results on the Hardness of $H$-free Edge Modification Problems
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- Subexponential Parameterized Algorithm for Minimum Fill-In
- A Subexponential Parameterized Algorithm for Proper Interval Completion
This page was built for publication: A cubic vertex-kernel for \textsc{Trivially Perfect Editing}