Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion

DOI10.4230/LIPIcs.IPEC.2015.365zbMath1378.68092OpenAlexW2253699097MaRDI QIDQ5363789

Naveen Sivadasan, R. B. Sandeep

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)

Related Items (12)

Parameterizing edge modification problems above lower bounds ⋮ Kernel for \(K_t\)\textsc{-free Edge Deletion} ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ Dichotomy Results on the Hardness of $H$-free Edge Modification Problems ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Unnamed Item ⋮ A Polynomial Kernel for Diamond-Free Editing ⋮ Aspects of upper defensive alliances ⋮ A polynomial kernel for trivially perfect editing ⋮ Polynomial kernels for paw-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

This page was built for publication: Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion