On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}

DOI10.1007/s00453-016-0215-yzbMath1380.68211OpenAlexW2786060560MaRDI QIDQ1679221

R. B. Sandeep, Naveen Sivadasan, N. R. Aravind

Publication date: 9 November 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-016-0215-y

zbMATH Keywords

bounded-degree graphspolynomial kernelizationedge deletion problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

A survey of parameterized algorithms and the complexity of edge modification ⋮ Declawing a graph: polyhedra and branch-and-cut algorithms ⋮ Incompressibility of \(H\)-free edge modification problems: towards a dichotomy

Cites Work

• Unnamed Item
• Cluster editing with locally bounded modifications
• Graph-modeled data clustering: Exact algorithms for clique generation
• On stable cutsets in claw-free graphs and planar graphs
• The node-deletion problem for hereditary properties is NP-complete
• Some simplified NP-complete graph problems
• Some complexity results about threshold graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• The maximum edge biclique problem is NP-complete
• A polynomial kernel for trivially perfect editing
• Cluster graph modification problems
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Incompressibility of \(H\)-free edge modification problems
• Faster parameterized algorithms for deletion to split graphs
• Additive approximation for edge-deletion problems
• NP-completeness results for edge modification problems
• Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems
• Compressing Bounded Degree Graphs
• Polynomial Kernelization for Removing Induced Claws and Diamonds
• On Generating Triangle-Free Graphs
• BOUNDED SEARCH TREE ALGORITHMS FOR PARAMETRIZED COGRAPH DELETION: EFFICIENT BRANCHING RULES BY EXPLOITING STRUCTURES OF SPECIAL GRAPH CLASSES
• Two Edge Modification Problems without Polynomial Kernels
• The complexity of some edge deletion problems
• Edge-Deletion Problems
• Computing the Minimum Fill-In is NP-Complete
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Parameterized Algorithms
• Characterizations of derived graphs
• Complexity classification of some edge modification problems

This page was built for publication: On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}