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

DOI10.1007/S00453-016-0215-YMaRDI QIDQ1679221zbMATH OpenOpenAlexFDO

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

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 graphsedge deletion problemspolynomial kernelization

Mathematics Subject Classification ID

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

Recommendations

• On Polynomial Kernelization of $$\mathcal {H}$$-free Edge Deletion
• Two edge modification problems without polynomial kernels
• Two edge modification problems without polynomial kernels
• Compressing Bounded Degree Graphs
• Kernel for \(K_t\)\textsc-free Edge Deletion

Cites work

• Additive approximation for edge-deletion problems
• Bounded search tree algorithms for parametrized cograph deletion: efficient branching rules by exploiting structures of special graph classes
• Characterizations of derived graphs
• Cluster editing with locally bounded modifications
• Cluster graph modification problems
• Complexity classification of some edge modification problems
• Compressing Bounded Degree Graphs
• Computing the Minimum Fill-In is NP-Complete
• Edge-Deletion Problems
• Faster parameterized algorithms for deletion to split graphs
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Graph-modeled data clustering: Exact algorithms for clique generation
• scientific article; zbMATH DE number 3668651 (Why is no real title available?)
• Incompressibility of \(H\)-free edge modification problems
• NP-completeness results for edge modification problems
• On generating triangle-free graphs
• On stable cutsets in claw-free graphs and planar graphs
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Parameterized algorithms
• Parameterized lower bound and improved kernel for diamond-free edge deletion
• Parameterized lower bounds and dichotomy results for the NP-completeness of H-free edge modification problems
• Polynomial kernelization for removing induced claws and diamonds
• Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
• Some complexity results about threshold graphs
• Some simplified NP-complete graph problems
• The complexity of some edge deletion problems
• The maximum edge biclique problem is NP-complete
• The node-deletion problem for hereditary properties is NP-complete
• Two edge modification problems without polynomial kernels

Cited in

(8)

• Declawing a graph: polyhedra and branch-and-cut algorithms
• Incompressibility of \(H\)-free edge modification problems: towards a dichotomy
• Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations
• Kernel for \(K_t\)\textsc-free Edge Deletion
• Polynomial kernelization for removing induced claws and diamonds
• On Polynomial Kernelization of $$\mathcal {H}$$-free Edge Deletion
• On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems
• A survey of parameterized algorithms and the complexity of edge modification

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

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