Temporality, geometry, and efficient algorithms of graphs
Les réseaux spatiotemporels (spatiotemporal networks, STN) sont des réseaux dont les attributs changent en fonction du temps tout en respectant certaines propriétés géométriques. Écrire des algorithmes sur les STNs est à l'intersection des graphes (N), de l'algorithmique du texte (T), et de l'algèbre (S).
Je présente un aperçu du travail mené ces 15 dernières années, au sujet de ces trois composants (N) (S) (T). Un point fédérateur est dans la notion de module de graphes, ainsi que de sommets jumeaux. Ces notions modélisent aussi bien les doublons dans un graphe que l'opération de factorisation de sommets.
- (N) Le premier composant s'adresse à la théorie des graphes: je présenterai une étude comparative des aspects algorithmiques des décompositions de graphes définies par largeur inspirée des modules: largeur de clique, largeur bimodulaire, largeur de rang, et largeur booléenne.
- (T) Le deuxième composant explore l'extension des graphes aux graphes temporels: alors que la plupart des versions temporelles des problèmes polynomiaux deviennent NP-difficiles à calculer (couplage, composant connexe, arbre couvrant ...), je présenterai des résultats polynomiaux calculant deux versions temporelles des modules, obtenus en examinant plutôt la négation du test d'un module au lieu du module lui-même.
- (S) Le dernier composant ouvre des directions futures aux études sur les aspects algébriques des graphes et des graphes temporels: deux résultats exploratoires seront présentés, un en utilisant la géométrie euclidienne et un en utilisant des propriétés de corps gauches.
La présentation terminera avec quelques perspectives dégagées après ces études, prises dans un ordre antichronologique sur les trois composants: (S) (T) (N).
Soutenance : 09/11/2023
Membres du jury :
Thomas Erlebach, Durham University [rapporteur]
Arnaud Casteigts, Université de Genève [rapporteur]
Reza Naserasr, CNRS, [rapporteur]
Olivier Bodini, Université Sorbonne Paris Nord
Roland Grappe, Université Paris Dauphine
Maria Potop-Butucaru, Sorbonne Université
Nicolas Trotignon, CNRS
Laurent Viennot, INRIA