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...
|Published in:||Algorithmica : an international journal in computer science, Vol. 71, No. 3 (2015), p. 702-730|
|Other Involved Persons:||; ; ;|
|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”.|
|QR Code:||Show QR Code|