Tempogral – Problèmes algorithmiques sur les graphes temporels

• Tempogral

Nom complet : Problèmes algorithmiques sur les graphes temporels

Financeur : ANR et France Relance (Next Gen UE)

Montant du financement : 166 677,76€

Période de réalisation : 01/10/2022 – 30/03/2027

Laboratoire : LITIS

Responsable scientifique : Eric Sanlaville

Coordinateur scientifique : Université de Bordeaux (Arnaud Casteigts)

Durée du projet : 54 mois

Descriptif du projet : Les graphes sont un outil de modélisation fondamental en science. Ils ont été utilisés pour modéliser des phénomènes dans des domaines allant de la physique statistique aux réseaux de communication, en passant par les algorithmes distribués, la logistique, la biologie, la médecine et les réseaux sociaux. Malgré de grands succès dans ces domaines, de nombreux phénomènes du monde réel sont dynamiques et dépassent l’expressivité des graphes standard. Au cours des deux dernières décennies, un intérêt croissant a été porté aux graphes temporels (aussi appelés graphes variants dans le temps, dépendants du temps, évolutifs ou simplement dynamiques), dans lesquels la présence d’arêtes et (parfois) de nœuds dépend du temps. L’utilisation de graphes temporels dans les domaines précédents a conduit à une prolifération de nouveaux concepts et questions algorithmiques, dont certains sont spécifiques et d’autres plus généraux. L’objectif de notre projet est de développer une théorie fondamentale (indépendante du domaine) des graphes temporels, en mettant l’accent sur la caractérisation/classification/résolution de problèmes algorithmiques intrinsèquement temporels. Le projet comporte trois axes, qui sont (1) la classification, (2) la tractabilité et (3) les techniques algorithmiques.

Retrouvez le résumé complet sur le site du LABRI.