Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations

DOI10.1016/j.tcs.2022.01.007OpenAlexW4205506269MaRDI QIDQ2077398

Huan Peng, Yongjie Yang, Wenjun Li

Publication date: 21 February 2022

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

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

zbMATH Keywords

clawdiamondkernelizationedge deletionFPT-algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Graph modification problem for some classes of graphs
• Fundamentals of parameterized complexity
• On making a distinguished vertex of minimum degree by vertex deletion
• Exact exponential algorithms.
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Edge deletion problems: branching facilitated by modular decomposition
• Polynomial kernelization for removing induced claws and diamonds
• Obtaining a planar graph by vertex deletion
• Parameterized complexity of Eulerian deletion problems
• Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
• Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion

This page was built for publication: Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations