A completeness theory for polynomial (Turing) kernelization

DOI10.1007/978-3-319-03898-8_18MaRDI QIDQ2867084zbMATH OpenOpenAlexFDO

Authors Danny Hermelin, Stefan Kratsch, Karolina Sołtys, Magnus Wahlström, Xi Wu

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_18

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• A completeness theory for polynomial (Turing) kernelization
• A hierarchy of polynomial kernels
• On problems without polynomial kernels
• On Problems without Polynomial Kernels (Extended Abstract)
• Kernelization Lower Bounds by Cross-Composition

Cited in

(5)

• Polynomial kernels and user reductions for the workflow satisfiability problem
• scientific article; zbMATH DE number 7053262 (Why is no real title available?)
• A completeness theory for polynomial (Turing) kernelization
• Reoptimization of parameterized problems
• A polynomial Turing-kernel for weighted independent set in bull-free graphs

This page was built for publication: A completeness theory for polynomial (Turing) kernelization

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