Lower bounds for kernelization

DOI10.1007/978-3-319-13524-3_1MaRDI QIDQ2946003zbMATH OpenOpenAlexWikidataFDO

Authors Hans L. Bodlaender

Publication date 15 September 2015

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

Full work available at URL https://doi.org/10.1007/978-3-319-13524-3_1

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Lower bounds on kernelization
• Kernelization: new upper and lower bound techniques
• STACS 2005
• On Problems without Polynomial Kernels (Extended Abstract)
• On problems without polynomial kernels

Cited in

(24)

• Lower bounds for kernelizations and other preprocessing procedures
• Lower bounds for kernelizations and other preprocessing procedures
• Kernelization: new upper and lower bound techniques
• Kernelization Lower Bounds by Cross-Composition
• Lower bounds for Haar projections: deterministic examples
• Lower bounds for separable approximations of the Hilbert kernel
• On problems without polynomial kernels
• On Problems without Polynomial Kernels (Extended Abstract)
• scientific article; zbMATH DE number 7053262 (Why is no real title available?)
• Search-space reduction via essential vertices
• Lower bounds on kernelization
• Kernelization lower bounds through colors and IDs
• STACS 2005
• Kernelization lower bounds for finding constant-size subgraphs
• Computing kernels in parallel: lower and upper bounds
• Fractals for kernelization lower bounds, with an application to length-bounded cut problems
• Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
• Algorithmic Learning Theory
• Kernels: Annotated, Proper and Induced
• Kernelization techniques and its applications to parameterized computation
• Incompressibility through Colors and IDs
• Fractals for kernelization lower bounds
• Cross-composition: a new technique for kernelization lower bounds
• A hierarchy of polynomial kernels

This page was built for publication: Lower bounds for kernelization

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