Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs

DOI10.1007/978-3-642-31155-0_32MaRDI QIDQ2904571zbMATHOpenAlexFDO

Authors Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai, Venkatesh Raman

Publication date 14 August 2012

Published in Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-31155-0_32

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)

Recommendations

• Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
• Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem
• Co-Nondeterminism in Compositions
• Kernelization Lower Bounds by Cross-Composition
• scientific article; zbMATH DE number 1696630

Cited in

(3)

• FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
• Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem
• Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs

This page was built for publication: Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs

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