A Completeness Theory for Polynomial (Turing) Kernelization

The framework of Bodlaender et al. (J Comput Sys Sci 75(8):423–434, 2009) and Fortnow and Santhanam (J Comput Sys Sci 77(1):91–106, 2011) allows us to exclude the existence of polynomial kernels for a range of problems under reasonable complexity-theoretical assumptions. However, some issues are not...

Full description

Bibliographic Details
Published in:Algorithmica : an international journal in computer science, Vol. 71, No. 3 (2015), p. 702-730
Main Author: Hermelin, Danny
Other Involved Persons: Kratsch, Stefan ; Sołtys, Karolina ; Wahlström, Magnus ; Wu, Xi
Format: electronic Article
Language:English
ISSN:1432-0541
Item Description:Main work done while Danny Hermelin and Magnus Wahlström were at the Max Planck Institute for Informatics. Main work done while Stefan Kratsch was supported by the Netherlands Organization for Scientific Research (NWO), Project "KERNELS: Combinatorial Analysis of Data Reduction”.
Physical Description:Online-Ressource
DOI:10.1007/s00453-014-9910-8
Subjects:
QR Code: Show QR Code