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

(27)

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

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)