A Polynomial Kernel for Line Graph Deletion
From MaRDI portal
Publication:5874512
DOI10.4230/LIPICS.ESA.2020.42OpenAlexW3081984875MaRDI QIDQ5874512FDOQ5874512
Authors: Eduard Eiben, William Lochet
Publication date: 7 February 2023
Full work available at URL: https://arxiv.org/abs/2006.15584
Cites Work
- Fundamentals of parameterized complexity
- Fixed-parameter tractability of graph modification problems for hereditary properties
- The node-deletion problem for hereditary properties is NP-complete
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Parametrized complexity theory.
- Congruent Graphs and the Connectivity of Graphs
- Parameterized Algorithms
- Title not available (Why is that?)
- Characterizations of derived graphs
- On the complexity of \(k\)-SAT
- Intersection Theorems for Systems of Sets
- Claw-free graphs. IV: Decomposition theorem
- Edge-Deletion Problems
- The complexity of some edge deletion problems
- On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
- Incompressibility of \(H\)-free edge modification problems
- Two edge modification problems without polynomial kernels
- Polynomial kernelization for removing induced claws and diamonds
- Dichotomy Results on the Hardness of $H$-free Edge Modification Problems
- A dynamic algorithm for line graph recognition
Cited In (7)
- Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
- A survey of parameterized algorithms and the complexity of edge modification
- A polynomial kernel for distance-hereditary vertex deletion
- A Polynomial Kernel for Proper Interval Vertex Deletion
- Polynomial Kernel for Interval Vertex Deletion
- Polynomial kernelization for removing induced claws and diamonds
- A polynomial kernel for block graph 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)