Parameterized lower bound and improved kernel for diamond-free edge deletion

DOI10.4230/LIPICS.IPEC.2015.365MaRDI QIDQ5363789zbMATH OpenOpenAlexFDO

Authors R. B. Sandeep, Naveen Sivadasan

Publication date 29 September 2017

Full work available at URL http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.365

zbMATH Keywords

polynomial kernelizationedge deletion problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Polynomial kernelization for removing induced claws and diamonds
• Polynomial kernelization for removing induced claws and diamonds
• A Polynomial Kernel for Diamond-Free Editing
• A polynomial kernel for diamond-free editing
• On Polynomial Kernelization of $$\mathcal {H}$$-free Edge Deletion

Cited in

(14)

• Edge deletion preserving the diameter of the hypercube
• Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem
• Kernel for \(K_t\)\textsc-free Edge Deletion
• Aspects of upper defensive alliances
• A Polynomial Kernel for Diamond-Free Editing
• scientific article; zbMATH DE number 7764101 (Why is no real title available?)
• Isolation of the diamond graph
• A survey of parameterized algorithms and the complexity of edge modification
• Polynomial kernels for paw-free edge modification problems
• On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
• Dichotomy results on the hardness of \(H\)-free edge modification problems
• A polynomial kernel for diamond-free editing
• Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations
• Polynomial kernelization for removing induced claws and diamonds

This page was built for publication: Parameterized lower bound and improved kernel for diamond-free edge deletion

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