Polynomial Kernelization for Removing Induced Claws and Diamonds

DOI10.1007/978-3-662-53174-7_31zbMath1362.68104OpenAlexW2522597737MaRDI QIDQ2827828

Michał Pilipczuk, Marcin Pilipczuk, Erik Jan van Leeuwen, Marek Cygan, 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

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 (4)

Dealing with several parameterized problems by random methods ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ Improved Algorithms for Several Parameterized Problems Based on Random Methods ⋮ A polynomial kernel for trivially perfect editing

Cites Work

• Unnamed Item
• Parameterized complexity of induced graph matching on claw-free graphs
• Cluster editing with locally bounded modifications
• Claw-free graphs. IV: Decomposition theorem
• Claw-free graphs. V. Global structure
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Which problems have strongly exponential complexity?
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Polynomial kernelization for removing induced claws and diamonds
• Incompressibility of H-Free Edge Modification
• Faster Parameterized Algorithms for Deletion to Split Graphs
• Two Edge Modification Problems without Polynomial Kernels
• Line Graphs of Helly Hypergraphs
• A Polynomial Kernel for Proper Interval Vertex Deletion
• Subexponential Parameterized Algorithm for Minimum Fill-In
• Characterizations of derived graphs
• A Subexponential Parameterized Algorithm for Proper Interval Completion

This page was built for publication: Polynomial Kernelization for Removing Induced Claws and Diamonds