Timothée est enseignant-chercheur contractuel à Université d’Orléans.
Titre : Explorer la complexité à travers des contraintes sur les graphes.
Résumé :
De la domination à la recherche de motifs, des tournées contraintes aux parcours colorés, ce séminaire explore comment ajouter une petite contrainte peut faire passer un problème de trivial à difficile (NP-complet voire inapproximable).
Qu’il s’agisse d’obligations de sélection, de motifs colorés, de transitions imposées ou de crédits à consommer dans un ordre précis, nous verrons comment ces contraintes créent des dépendances non locales qui rendent les problèmes difficiles même sur des graphes très simples (chemins, faibles diamètres, complets).
Bio : Timothée Martinod a fait sa thèse, intitulée « Étude de complexité algorithmique pour des problèmes de domination et de tournées dans les graphes avec obligations », sous la direction de Christian Laforest à l’université Clermont Auvergne. Actuellement, Timothée est enseignant-chercheur contractuel
à Université d’Orléans.