Further parameterized algorithms for the F-free edge deletion problem

DOI10.1016/J.TCS.2022.08.025OpenAlexW4294862349MaRDI QIDQ2676471FDOQ2676471

Authors: Ajinkya Gaikwad, Soumen Maity 

Publication date: 27 September 2022

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2022.08.025

Recommendations

• Parameterized lower bound and NP-completeness of some \(H\)-free edge deletion problems
• Parameterized algorithms for deletion to \((r,\ell)\)-graphs
• The complexity of some edge deletion problems
• A parameterized algorithm for bounded-degree vertex deletion
• Parameterized algorithms on perfect graphs for deletion to \((r,\ell)\)-graphs
• Parameterized lower bound and improved kernel for diamond-free edge deletion
• On structural parameterizations of the bounded-degree vertex deletion problem
• On structural parameterizations of the bounded-degree vertex deletion problem
• Faster parameterized algorithms for two vertex deletion problems
• Fixed-treewidth-efficient algorithms for edge-deletion to interval graph classes

zbMATH Keywords

treewidthparameterized complexityFPTvertex cover numberW[1-hard]

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Fixed-parameter tractability of graph modification problems for hereditary properties
• A unified approximation algorithm for node-deletion problems
• Which problems have strongly exponential complexity?
• Integer Programming with a Fixed Number of Variables
• Minkowski's Convex Body Theorem and Integer Programming
• Parameterized algorithms
• Title not available (Why is that?)
• Node-and edge-deletion NP-complete problems
• Title not available (Why is that?)
• On the hardness of approximating minimization problems
• Complexity classification of some edge modification problems
• Graph Layout Problems Parameterized by Vertex Cover
• Graph minors. III. Planar tree-width
• On the NP-hardness of edge-deletion and -contraction problems
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• Faster parameterized algorithms for deletion to split graphs

Cited In (1)

• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs

This page was built for publication: Further parameterized algorithms for the \(\mathcal{F}\)-free edge deletion problem

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