Séminaire

Possibilité de visioconférence

Reconfigurer une solution d’un problème donné, c’est lui appliquer des opérations élémentaires successives sans quitter l’espace des solutions. Un tel besoin apparaît naturellement dans des situations dynamiques où une solution donnée est déjà en place et doit être modifiée, sans qu’une rupture de service puisse être envisagée. Plusieurs grandes questions sont étudiées : quelles opérations élémentaires garantissent que toute autre solution peut être ainsi atteinte ? À opérations fixées, quelle est la complexité de décider si une autre solution donnée peut être atteinte ? Que dire du nombre d’opérations nécessaires pour cela ?
Dans cet exposé, nous discuterons de divers résultats positifs et négatifs autour de problèmes de graphes.