Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Recent Developments in the Theory of Pre-Processing

Fellows, Michael (2011). Recent Developments in the Theory of Pre-Processing. In: Joint Conference of FAW2011 and AAIM, Jinhua, China, 28-31 May 2011.

Document type: Conference Paper
Citation counts: Google Scholar Search Google Scholar

IRMA ID CDU0002xPUB38
Author Fellows, Michael
Title Recent Developments in the Theory of Pre-Processing
Conference Name Joint Conference of FAW2011 and AAIM
Conference Location Jinhua, China
Conference Dates 28-31 May 2011
Conference Publication Title Proceedings of the Joint Conference of FAW2011 and AAIM
Place of Publication Germany
Publisher Springer
Publication Year 2011
Volume Number 6681 LNCS
ISBN 9783642212031   (check CDU catalogue open catalogue search in new window)
ISSN 0302-9743   (check CDU catalogue open catalogue search in new window)
Start Page 4
End Page 5
Total Pages 2
HERDC Category E3 - Conference Publication - Extract of paper (internal)
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.
Additional Notes Series Title: Lecture Notes in Computer Science, v. 6681
 
Versions
Version Filter Type
Access Statistics: 68 Abstract Views  -  Detailed Statistics
Created: Fri, 17 Jan 2014, 00:16:44 CST