A Polynomial Kernel for Line Graph Deletion

DOI10.4230/LIPIcs.ESA.2020.42OpenAlexW3081984875MaRDI QIDQ5874512

William Lochet, Eduard Eiben

Publication date: 7 February 2023

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

zbMATH Keywords

line graphskernelizationgraph modification problem\(H\)-free editing

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (1)

A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Claw-free graphs. IV: Decomposition theorem
• The node-deletion problem for hereditary properties is NP-complete
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• 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
• Polynomial kernelization for removing induced claws and diamonds
• Parametrized complexity theory.
• Intersection Theorems for Systems of Sets
• The complexity of some edge deletion problems
• Edge-Deletion Problems
• Congruent Graphs and the Connectivity of Graphs
• Dichotomy Results on the Hardness of $H$-free Edge Modification Problems
• Parameterized Algorithms
• Characterizations of derived graphs
• On the complexity of \(k\)-SAT
• A dynamic algorithm for line graph recognition

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