Un tour d'horizon des décompositions arborescentes

Frédéric Mazoit
Université de Marseille II


Résumé:

Au cours des années 80, Robertson et Seymour ont mené à terme un ambitieux projet sur les mineurs de graphes. Pour cela, ils ont défini, entre autre, les décompositions arborescentes. Ces décompositions se sont avérées avoir des applications algorithmiques importantes. Au cours de cet exposé, je ferai une présentation chronologique des problèmes qui ont motivé l'introduction de ces décompositions et des principaux travaux qui ont été effectué dans ce domaine. Dans un second temps, j'évoquerai certaines applications récentes de ces décompositions aux matroïdes.

Retour au séminaire