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

DOI10.1007/978-3-642-31155-0_32zbMATH Open1357.68073OpenAlexW72161672MaRDI QIDQ2904571FDOQ2904571

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

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

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)

Cited In (2)

• Kernel lower bounds using co-nondeterminism: finding induced hereditary subgraphs
• FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders

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)