Incompressibility of H-free edge modification

DOI10.1007/978-3-319-03898-8_9zbMATH Open1309.68086OpenAlexW938002210MaRDI QIDQ2867075FDOQ2867075

Authors: Leizhen Cai, Yufei Cai 

Publication date: 10 December 2013

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-03898-8_9

Recommendations

• Incompressibility of \(H\)-free edge modification problems
• Two edge modification problems without polynomial kernels
• Two edge modification problems without polynomial kernels
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Hardness of approximation for \(H\)-free edge modification problems

Mathematics Subject Classification ID

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

Cited In (8)

• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Two edge modification problems without polynomial kernels
• Incompressibility of \(H\)-free edge modification problems
• Polynomial kernels for paw-free edge modification problems
• Two edge modification problems without polynomial kernels
• Hardness of approximation for \(H\)-free edge modification problems
• Hardness of approximation for \(H\)-free edge modification problems
• Polynomial kernelization for removing induced claws and diamonds

This page was built for publication: Incompressibility of \(H\)-free edge modification

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