Conférence
Notice
Langue :
Anglais
Crédits
INRIA (Institut national de recherche en informatique et automatique) (Publication), Région PACA (Production), VSP - Vidéo Sud Production (Réalisation), INRIA (Institut national de recherche en informatique et automatique) (Production), UNS (Publication), CNRS - Centre National de la Recherche Scientifique (Publication), Fedor V. Fomin (Intervention)
Conditions d'utilisation
Droit commun de la propriété intellectuelle
DOI : 10.60527/8tps-bh74
Citer cette ressource :
Fedor V. Fomin. Inria. (2011, 17 novembre). Introduction to Kernelization. [Vidéo]. Canal-U. https://doi.org/10.60527/8tps-bh74. (Consultée le 19 mars 2024)

Introduction to Kernelization

Réalisation : 17 novembre 2011 - Mise en ligne : 22 novembre 2011
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

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. 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.

Intervention

Sur le même thème