Paper Info
Title
Recent developments in the theory of pre-processing
Abstract
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.
Year
DOI
Venue
2011
10.1007/978-3-642-21204-8_2
FAW-AAIM
Field
DocType
Volume
Kernelization,Combinatorics,Parameterized complexity,Algorithmics,Theoretical computer science,Time complexity,Mathematics,Computational complexity theory
Conference
6681
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
0
1
Name
Order
Citations
PageRank
Michael R. Fellows14138319.37