A cubic vertex-kernel for \textsc{Trivially Perfect Editing}

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

zbMATH Keywords

parameterized complexity graph modification problems kernelization algorithms trivially perfect graphs

Mathematics Subject Classification ID

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

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}