Soutenance de thèse de Bastien Sérée
15 décembre 2022 @ 10 h 00 min
Bastien Sérée, doctorant au sein de l’équipe STR, soutiendra sa thèse intitulée :
« Problèmes d’optimisation dans les graphes paramétrés » / « Optimisation problems in parametrized graphs »
Le 15 décembre 2022 à 10h, dans l’amphithéâtre B 008, sur le site de l’École Centrale
Jury :
– Directeur de thèse : Didier Lime
– Encadrant : Loïg Jezequel
– Examinateur·rice·s : Nathalie Sznajder, Nicolas Markey, Stéphane Le Roux, Pierre-Alain Reynier et Etienne André
– Rapporteurs : Pierre-Alain Reynier et Etienne André
Nous considérons des graphes orientés pondérés dont l’énergie est paramétrée. Nous proposons dans un premier temps un algorithme qui, étant donné un graphe et un de ses sommets, renvoie des arbres, chaque arbre représentant les plus courts chemins depuis la source vers tous les autres sommets du graphe pour une zone particulière de l’espace des paramètres. De plus l’union de ces zones couvre l’espace des paramètres. Nous considérons ensuite l’accessibilité dans les graphes à énergie multi-dimensionnelle, avec un type de contraintes plus absolues qui imposent que l’énergie reste entre des bornes. Nous montrons la décidabilité et la complexité du problème quel que soit le nombre de paramètres et de dimensions lorsque les paramètres prennent des valeurs entières. Nous montrons également l’indécidabilité de ce problème avec au moins un paramètre lorsque la dimension est supérieure ou égale à deux. Nous étudions enfin des jeux de parité à un et deux joueurs sur les graphes paramétrés dont l’objectif est la conjonction d’une condition qualitative sur la parité et d’une condition quantitative : l’énergie doit rester positive. Nous montrons la décidabilité et prouvons des bornes de la complexité du problème de la recherche d’une stratégie gagnante dans les cas à un et à deux joueurs.
Mots-clés : automate, graphes paramétrés, plus court chemin, jeux sur les graphes, objectifs de parité, contraintes sur l’énergie, model-checking.
Keywords: automata, parametrized graphs, shortest paths, games on graphs, parity objectives, energy constraints, model-checking
