Problèmes algorithmiques sur les graphes temporels – TEMPOGRAL

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 susmentionnés 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.