Il y a dix ans, Sylvain Guillemot et Dániel Marx résolvaient un problème ouvert notable sur la recherche de motif efficace dans une permutation. Pour ce faire, ils introduisent une nouvelle décomposition de permutations et un paramètre associé. Guillemot et Marx concluent leur introduction en observant qu'"il serait intéressant de voir s'il existe un analogue sur les graphes correspondant à ce schéma".
Il y a quatre ans, avec mes collègues Eunjung Kim, Stéphan Thomassé et Rémi Watrigant, nous avons en effet étendu cette "largeur" de permutations aux graphes et, plus généralement, aux structures binaires. Avec plusieurs collaborateurs, nous avons exploré les applications de ce nouvel invariant de graphes, appelé twin-width. Le mémoire est consacré au résumé de nos explorations. Nous y voyons que la twin-width est un paramètre très général, orthogonal à l'organisation actuelle de la théorie des graphes. Les classes de twin-width bornée admettent des propriétés structurelles, des algorithmes efficaces pour une grande famille de problèmes, ainsi que des caractérisations par la logique.
Ces résultats sont en partie complètement nouveaux, et en partie viennent généraliser et unifier des faits constatés isolément sur des classes particulières à twin-width bornée. La twin-width a une grande importance sur les structures binaires totalement ordonnées, où la démarcation "twin-width bornée"/"twin-width non bornée" correspond exactement à des frontières importantes en algorithmique, théorie des modèles, et combinatoire énumérative.
Devant un jury composé de :
- Monsieur Thomas COLCOMBET
- Monsieur Frédéric HAVET
- Monsieur David EPPSTEIN
- Madame Angela BONIFATI
- Madame Claire MATHIEU
- Monsieur Bruno SALVY
Gratuit
Disciplines