Soutenance de thèse d'Alice Joffard (ROSP) mercredi 25 novembre 2020 à 14h, en visioconférence
Intitulée : "Domination de graphes et problèmes de reconfiguration"
La soutenance sera retransmise sur Youtube Live, via le lien : Lien vers le site
L'exposé sera en français, mais une vidéo de la version en anglais sera disponible ensuite sur la page web de Alice Joffard.
Les membres du jury :
Résumé :
Cette thèse a pour objet l'étude de la domination de graphes et des problèmes de reconfiguration.
Un ensemble dominant d'un graphe est un sous-ensemble de sommets tel que tous les sommets du graphe sont ou bien dans l'ensemble, ou bien sont voisins d'au moins un sommet dans l'ensemble. Quant aux problèmes de reconfiguration, ils consistent, étant donné un problème source, à étudier si il est possible, et comment, de passer d'une solution de ce problème source à une autre en effectuant une séquence de changements élémentaires suivant une règle donnée qui maintiennent une solution.
Cette thèse étudie la reconfiguration d'ensembles dominants dans un graphe, selon deux règles distinctes: l'ajout/suppression de jeton, et le glissement de jeton. Avec la règle d'ajout/suppression de jeton, nous étudions la connexité du graphe de reconfiguration. Avec la règle de glissement de jeton, nous étudions la complexité du problème qui consiste, étant donnés deux ensembles dominants, à déterminer s'il existe une séquence de reconfiguration entre les deux. Nous présentons ensuite des résultats sur la domination éternelle, qui peut être décrite comme une version à deux joueurs de la reconfiguration d'ensembles dominants sous la règle du glissement de jeton. Enfin, nous étudions la reconfiguration de graphes ayant la même séquence de degrés.
LIEN TEMPORAIRE VERS LE MANUSCRIT
I am pleased to invite you to my thesis defense entitled: "Graph domination and reconfiguration problems".
It will take place on Wednesday, November 25, 2020 at 2 pm, in visioconference. It will be casted on Youtube Live, on the following link: weblink
The presentation will be in French, but a video of the presentation in english will be available on the webpage afterwards.
The jury is composed of :
Abstract :
This object of this thesis is to study graph domination and reconfiguration problems.
A dominating set of a graph is a subset of vertices such that every vertex of the graph either is in the set, or is a neighbor of at least one vertex in the set. As for reconfiguration problems, they consist in, given a source problem, determining if it is possible, and how, to go from a solution of this source problem to another by performing a sequence of elementary changes following a given rule and that maintain a solution all along.
This thesis studies the reconfiguration of dominating sets in a graph, under two distinct rules: the token addition-removal rule, and the token sliding rule. With the token addition-removal rule, we study the connectivity of the reconfiguration graph. With the token sliding rule, we study the complexity of the problem which consists in, given two dominating sets, determining if there exists a reconfiguration sequence between the two. We then present some results about eternal domination, that can be described as a two players version of the reconfiguration of dominating sets under the token sliding rule. Finally, we study the reconfiguration of graphs with the same degree sequence.
TEMPORARY LINK TO THE DISSERTATION
L'exposé sera en français, mais une vidéo de la version en anglais sera disponible ensuite sur la page web de Alice Joffard.
Les membres du jury :
- Mr Liedloff Mathieu, maître de conférences à l'université d'Orléans (rapporteur)
- Mr Togni Olivier, professeur à l'université de Bourgogne (rapporteur)
- Mme Bonifati Angela, professeure à l'université Lyon 1 (examinatrice)
- Mme Brauner Nadia, professeure à l'université Grenoble Alpes (examinatrice)
- Mme Meeks Kitty, chercheure à l'université de Glasgow (examinatrice)
- Mme Nishimura Naomi, professeure associée à l'université de Waterloo (examinatrice)
- Mr Kheddouci Hamamache, professeur à l'université Lyon 1 (directeur de thèse)
- Mr Bousquet Nicolas, chargé de recherche au CNRS de Lyon (co-directeur de thèse)
Résumé :
Cette thèse a pour objet l'étude de la domination de graphes et des problèmes de reconfiguration.
Un ensemble dominant d'un graphe est un sous-ensemble de sommets tel que tous les sommets du graphe sont ou bien dans l'ensemble, ou bien sont voisins d'au moins un sommet dans l'ensemble. Quant aux problèmes de reconfiguration, ils consistent, étant donné un problème source, à étudier si il est possible, et comment, de passer d'une solution de ce problème source à une autre en effectuant une séquence de changements élémentaires suivant une règle donnée qui maintiennent une solution.
Cette thèse étudie la reconfiguration d'ensembles dominants dans un graphe, selon deux règles distinctes: l'ajout/suppression de jeton, et le glissement de jeton. Avec la règle d'ajout/suppression de jeton, nous étudions la connexité du graphe de reconfiguration. Avec la règle de glissement de jeton, nous étudions la complexité du problème qui consiste, étant donnés deux ensembles dominants, à déterminer s'il existe une séquence de reconfiguration entre les deux. Nous présentons ensuite des résultats sur la domination éternelle, qui peut être décrite comme une version à deux joueurs de la reconfiguration d'ensembles dominants sous la règle du glissement de jeton. Enfin, nous étudions la reconfiguration de graphes ayant la même séquence de degrés.
LIEN TEMPORAIRE VERS LE MANUSCRIT
I am pleased to invite you to my thesis defense entitled: "Graph domination and reconfiguration problems".
It will take place on Wednesday, November 25, 2020 at 2 pm, in visioconference. It will be casted on Youtube Live, on the following link: weblink
The presentation will be in French, but a video of the presentation in english will be available on the webpage afterwards.
The jury is composed of :
- Mr Liedloff Mathieu, lecturer at the university of Orléans (rapporteur)
- Mr Togni Olivier, professor at the university of Bourgogne (rapporteur)
- Mme Bonifati Angela, professor at the university of Lyon 1 (examinatrice)
- Mme Brauner Nadia, professor at the university of Grenoble Alpes (examinatrice)
- Mme Meeks Kitty, research fellow at the university of Glasgow (examinatrice)
- Mme Nishimura Naomi, associate professor at the university of Waterloo (examinatrice)
- Mr Kheddouci Hamamache, professor at the university of Lyon 1 (PhD advisor)
- Mr Bousquet Nicolas, chargé de recherche au CNRS de Lyon (PhD advisor)
Abstract :
This object of this thesis is to study graph domination and reconfiguration problems.
A dominating set of a graph is a subset of vertices such that every vertex of the graph either is in the set, or is a neighbor of at least one vertex in the set. As for reconfiguration problems, they consist in, given a source problem, determining if it is possible, and how, to go from a solution of this source problem to another by performing a sequence of elementary changes following a given rule and that maintain a solution all along.
This thesis studies the reconfiguration of dominating sets in a graph, under two distinct rules: the token addition-removal rule, and the token sliding rule. With the token addition-removal rule, we study the connectivity of the reconfiguration graph. With the token sliding rule, we study the complexity of the problem which consists in, given two dominating sets, determining if there exists a reconfiguration sequence between the two. We then present some results about eternal domination, that can be described as a two players version of the reconfiguration of dominating sets under the token sliding rule. Finally, we study the reconfiguration of graphs with the same degree sequence.
TEMPORARY LINK TO THE DISSERTATION