Although pre-processing is a practical computing strategy almost universally employed for real-world attacks on NP-hard problems, it is perhaps surprising that for more than thirty years there has been no mathematically-disciplined theory of the subject. The parameterized/multivariate view of computational complexity makes such a theory possible, and this turns out to be deeply productive and useful. In the theory of parameterized complexity and algorithmics, the subject is termed kernelization. We survey the origins, recent developments and applications of the theory of polynomial-time kernelization. � 2011 Springer-Verlag.
|Number of pages
|Published - 2011
|Joint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2011) - Berlin, Germany, Berlin, Germany
Duration: 28 May 2011 → 31 May 2011
Conference number: 2011
|Joint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2011)
|28/05/11 → 31/05/11