Smaller kernels for 3-leaf power modifications problems

DOI10.1016/J.TCS.2025.115483MaRDI QIDQ6908099zbMATH OpenFDO

Authors Dekel Tsur

Publication date 1 November 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115483

zbMATH Keywords

graph algorithmskernelizationparameterized complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A 2k kernel for the cluster editing problem
• A characterization of ptolemaic graphs
• A fast branching algorithm for cluster vertex deletion
• A golden ratio parameterized algorithm for cluster editing
• A more effective linear kernelization for cluster editing
• A Polynomial Kernel for Proper Interval Vertex Deletion
• A survey of parameterized algorithms and the complexity of edge modification
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Applying modular decomposition to parameterized cluster editing problems
• Automated generation of search tree algorithms for hard graphs modification problems
• Bounded-degree techniques accelerate some parameterized graph algorithms
• Closest 4-leaf power is fixed-parameter tractable
• Cluster deletion revisited
• Cluster editing: kernelization based on edge cuts
• Completion to chordal distance-hereditary graphs: a quartic vertex-kernel
• Efficient Parameterized Preprocessing for Cluster Editing
• Error compensation in leaf power problems
• Even faster parameterized cluster deletion and cluster editing
• Faster parameterized algorithm for cluster vertex deletion
• Feedback vertex set inspired kernel for chordal vertex deletion
• Fixed-parameter algorithms for cluster vertex deletion
• Going weighted: parameterized algorithms for cluster editing
• Graph-modeled data clustering: Exact algorithms for clique generation
• scientific article; zbMATH DE number 7803579 (Why is no real title available?)
• scientific article; zbMATH DE number 7803591 (Why is no real title available?)
• Kernelization. Theory of parameterized preprocessing
• Polynomial kernels for 3-leaf power graph modification problems
• Recognizing k -Leaf Powers in Polynomial Time, for Constant k
• Subquadratic kernels for implicit 3-{\textsc{Hitting Set}} and 3-{\textsc{Set Packing}} problems

Cited in

(1)

• Faster algorithms for 3-leaf power modification problems

This page was built for publication: Smaller kernels for 3-leaf power modifications problems

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