Recent developments in the Theory of pre-processing

Michael Fellows

    Research output: Contribution to conferenceAbstract

    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. � 2011 Springer-Verlag.
    Original languageEnglish
    Number of pages2
    Publication statusPublished - 2011
    EventJoint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2011) - Berlin, Germany, Berlin, Germany
    Duration: 28 May 201131 May 2011
    Conference number: 2011

    Conference

    ConferenceJoint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2011)
    Abbreviated titleFAW AAIM
    CountryGermany
    CityBerlin
    Period28/05/1131/05/11

    Fingerprint Dive into the research topics of 'Recent developments in the Theory of pre-processing'. Together they form a unique fingerprint.

  • Cite this

    Fellows, M. (2011). Recent developments in the Theory of pre-processing. Abstract from Joint Conference of Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM 2011), Berlin, Germany.