scientific article; zbMATH DE number 7764101

DOI10.4230/lipics.ipec.2020.10arXiv1911.03683MaRDI QIDQ6089654

Eduard Eiben, William Lochet, Saket Saurabh

Publication date: 13 November 2023

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

kernelizationgraph modification problempaw-free graph\(H\)-free editing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (5)

On subgraph complementation to \(H\)-free graphs ⋮ Cutting a tree with subgraph complementation is hard, except for some small trees ⋮ Polynomial kernels for paw-free edge modification problems ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy ⋮ On subgraph complementation to \(H\)-free Graphs

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Claw-free graphs. IV: Decomposition theorem
• Paw-free graphs
• The node-deletion problem for hereditary properties is NP-complete
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Two edge modification problems without polynomial kernels
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Incompressibility of \(H\)-free edge modification problems
• Parametrized complexity theory.
• A Polynomial Kernel for Diamond-Free Editing
• Dichotomy Results on the Hardness of $H$-free Edge Modification Problems
• Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion
• Parameterized Algorithms

This page was built for publication: