Inria
Inria.fr
Inria Channel
Colloquium Jacques Morgenstern
Introduction to Kernelization
Preprocessing or data reductions means reducing the input to something simpler by solving an easy part of the input and this is the type of algorithms used in almost every application. In spite of wide practical applications of preprocessing, a systematic theoretical study of such algorithms remains elusive.
- Date : 17/11/2011
- Lieu : Inria Sophia Antipolis, Ampi Morgenstern
- Intervenants : Fedor Fomin (Université de Bergen, Norvège)
- Organisateurs : Inria, I3S, Université NIce Sophia Antipolis, CNRS, Polytech'Nice Sophia
The framework of parameterized complexity can be used as an approach to analyse preprocessing algorithms. Input to parameterized algorithms include a parameter (in addition to the input) which is likely to be small, and this resulted in a study of preprocessing algorithms that reduce the size of the input to a pure function of the parameter (independent of the input size). Such type of preprocessing algorithms are called kernelization algorithms. In the talk we give an overview of some classical and new techniques in the design of kernelization algorithms.
Localisation
Mots-clés : Kernelization algorithms Preprocessing Inria Sophia Antipolis - Méditerranée
Colloquium J. Morgenstern
Série de conférences mensuelles, le Colloquium Jacques Morgenstern expose les recherches les plus actives et les plus prometteuses dans le domaine des Sciences et Technologies de l’Information et de la Communication (STIC). Il est le fruit d'un partenariat entre le laboratoire I3S (UNS-CNRS), Polytech'Nice-Sophia et Inria.
