Stéphan THOMASSÉ

Statut

Professeur

Promotion

Senior 2016

Établissement

École normale supérieure de Lyon (ENSL)

Secteur disciplinaire

Sciences et Technologies de l'Information et de la Communication

Spécialité

Informatique Fondamentale

Thématique

Théorie des graphes
Algorithmique
Optimisation combinatoire

Présentation

Mon projet s'articule autour de deux thèmes :

Les décompositions de graphes. C'est un des outils principaux en théorie et algorithmique des structures discrètes. Le but est de décomposer les graphes en éléments plus simples, ou bien suivant un schéma global structuré Je m'intéresse principalement aux décomposition des graphes en ensembles stables (coloration de graphes), en chemins, en cycles, ou encore en arbres.

Les algorithmes avec paramètre fixé (FPT). Une application majeure des décompositions de graphes est la conception d'algorithmes polynomiaux, d'approximation ou paramétrés. Par exemple, l'introduction des algorithmes FPT découle de la notion de largeur arborescente de Robertson et Seymour. Mes recherches portent ici sur les algorithmes de compression (noyaux polynomiaux).