Polynomial kernelization for removing induced claws and diamonds

DOI10.1007/978-3-662-53174-7_31MaRDI QIDQ2827828zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Erik Jan van Leeuwen, Marcin Wrochna

Publication date 21 October 2016

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://dspace.library.uu.nl/handle/1874/361075

Mathematics Subject Classification ID

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

Recommendations

• Polynomial kernelization for removing induced claws and diamonds
• Parameterized lower bound and improved kernel for diamond-free edge deletion
• On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
• On Polynomial Kernelization of $$\mathcal {H}$$-free Edge Deletion
• A polynomial kernel for diamond-free editing

Cites work

• A Polynomial Kernel for Proper Interval Vertex Deletion
• A subexponential parameterized algorithm for proper interval completion
• Characterizations of derived graphs
• Claw-free graphs. IV: Decomposition theorem
• Claw-free graphs. V. Global structure
• Cluster editing with locally bounded modifications
• Exploring subexponential parameterized complexity of completion problems
• Faster parameterized algorithms for deletion to split graphs
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Incompressibility of H-free edge modification
• Line Graphs of Helly Hypergraphs
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Parameterized complexity of induced graph matching on claw-free graphs
• Polynomial kernelization for removing induced claws and diamonds
• Subexponential parameterized algorithm for minimum fill-in
• Two edge modification problems without polynomial kernels
• Which problems have strongly exponential complexity?

Cited in

(7)

• On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion}
• Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations
• Polynomial kernelization for removing induced claws and diamonds
• Dealing with several parameterized problems by random methods
• Improved algorithms for several parameterized problems based on random methods
• A Polynomial Kernel for Diamond-Free Editing
• Parameterized lower bound and improved kernel for diamond-free edge deletion

This page was built for publication: Polynomial kernelization for removing induced claws and diamonds

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