A polynomial kernel for 3-leaf power deletion

DOI10.1007/s00453-023-01129-9OpenAlexW2985186044MaRDI QIDQ6046945

O.-joung Kwon, Eduard Eiben, Jungho Ahn, Sang-il Oum

Publication date: 6 October 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2020/12676/

zbMATH Keywords

algorithmkernelizationvertex deletionparameterized\(\ell\)-leaf power

Mathematics Subject Classification ID

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

Cites Work

• Fundamentals of parameterized complexity
• Parameterized complexity of vertex deletion into perfect graph classes
• Improved upper bounds for vertex cover
• Parameterized leaf power recognition via embedding into graph products
• Structure and linear time recognition of 3-leaf powers
• Fixed-parameter algorithms for cluster vertex deletion
• The NLC-width and clique-width for powers of graphs of bounded tree-width
• Distance-hereditary graphs
• The node-deletion problem for hereditary properties is NP-complete
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• A kernel of order \(2k-c\log k\) for vertex cover
• Linear time solvable optimization problems on graphs of bounded clique-width
• The 4-Steiner Root problem
• A polynomial kernel for block graph deletion
• Some remarks about leaf roots
• Error compensation in leaf power problems
• On Graph Powers for Leaf-Labeled Trees
• The 3-Steiner Root Problem
• Decomposition of Directed Graphs
• Approximation and Kernelization for Chordal Vertex Deletion
• Feedback Vertex Set Inspired Kernel for Chordal Vertex Deletion
• Subquadratic Kernels for Implicit 3-H <scp>itting</scp> S <scp>et</scp> and 3-S <scp>et</scp> P <scp>acking</scp> Problems
• Kernelization
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Faster Parameterized Algorithms Using Linear Programming
• Structure and linear-time recognition of 4-leaf powers
• Interval Vertex Deletion Admits a Polynomial Kernel
• Parameterized Algorithms
• A polynomial kernel for distance-hereditary vertex deletion
• Unnamed Item

This page was built for publication: A polynomial kernel for 3-leaf power deletion