CE48 - Fondements du numérique: informatique, automatique, traitement du signal

Twin-width: théorie et applications – TWIN-WIDTH

Résumé de soumission

Le but de ce projet est d'explorer des questions algorithmiques et combinatoires liées à un nouvel invariant de graphes et de matrices, baptisé twin-width, introduit et développé par l'équipe. La twin-width a déjà permis d'avancer sur des questions en théorie algorithmique des graphes (comme celle de la complexité du model checking de formules du premier ordre sur des sous-classes de structures binaires) et en combinatoire (par exemple, sur la croissance des classes héréditaires de graphes ordonnés).
Les classes de twin-width bornée sont plutôt "orthogonales" à l'organisation actuelle de la théorie des graphes.
Elles comprennent les classes sans mineur fixé mais pas celles de degré borné, les graphes d'intervalles unitaires mais pas les graphes d'intervalles, ainsi que certaines classes d'expanseurs tandis que les graphes aléatoires cubiques ont presque sûrement twin-width élevée.
Les questions principales que nous allons attaquer concernent l'existence d'un algorithme approchant la twin-width, la généralisation de la notion à d'autres objets mathématiques, le calcul rapide sur des matrices de twin-width bornée, et la réinspection de problèmes classiques en combinatoire par le prisme de la twin-width.

Coordination du projet

Édouard Bonnet (Laboratoire d'Informatique du Parallélisme)

L'auteur de ce résumé est le coordinateur du projet, qui est responsable du contenu de ce résumé. L'ANR décline par conséquent toute responsabilité quant à son contenu.

Partenaire

LIP Laboratoire d'Informatique du Parallélisme

Aide de l'ANR 154 255 euros
Début et durée du projet scientifique : septembre 2021 - 48 Mois

Liens utiles

Explorez notre base de projets financés

 

 

L’ANR met à disposition ses jeux de données sur les projets, cliquez ici pour en savoir plus.

Inscrivez-vous à notre newsletter
pour recevoir nos actualités
S'inscrire à notre newsletter