A Polynomial Kernel for Line Graph Deletion

DOI10.4230/LIPICS.ESA.2020.42MaRDI QIDQ5874512zbMATH OpenOpenAlexFDO

Authors Eduard Eiben, William Lochet

Publication date 7 February 2023

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

zbMATH Keywords

\(H\)-free editinggraph modification problemkernelizationline graphs

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A dynamic algorithm for line graph recognition
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Characterizations of derived graphs
• Claw-free graphs. IV: Decomposition theorem
• Congruent Graphs and the Connectivity of Graphs
• Dichotomy results on the hardness of H-free edge modification problems
• Edge-Deletion Problems
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Incompressibility of \(H\)-free edge modification problems
• Intersection Theorems for Systems of Sets
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• On the complexity of k-SAT
• Parameterized algorithms
• Parametrized complexity theory.
• Polynomial kernelization for removing induced claws and diamonds
• The complexity of some edge deletion problems
• The node-deletion problem for hereditary properties is NP-complete
• Two edge modification problems without polynomial kernels

Cited in

(11)

• Polynomial kernelization for removing induced claws and diamonds
• A polynomial kernel for block graph deletion
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• A Polynomial Kernel for Proper Interval Vertex Deletion
• A polynomial kernel for distance-hereditary vertex deletion
• Polynomial Kernel for Interval Vertex Deletion
• A survey of parameterized algorithms and the complexity of edge modification
• Kernel for proper Helly circular-arc vertex deletion: smaller and simpler via graph isomorphism
• Polynomial kernel and incompressibility for prison-free edge deletion and completion
• A quadratic kernel for \{Claw, Diamond\}-free deletion
• Kernel for proper Helly circular-arc vertex deletion

This page was built for publication: A Polynomial Kernel for Line Graph Deletion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874512)