TEMPOGRAL [pdf]

Algorithmique des graphes temporels : modèles, questions, résolution

Temporal graph algorithms: models, questions, resolution

Supported by the French ANR, project ANR-22-CE48-0001 (TEMPOGRAL)

Réunions

Meetings

Partenaires

Partners

LaBRI, Université de Bordeaux
  • Arnaud CASTEIGTS (coord. global)
  • Timothée CORSINI
  • Cyril GAVOILLE
  • Nicolas HANUSSE
  • Colette JOHNEN
  • Ralf KLASING
LITIS, Université de Normandie
  • Stefan BALEV
  • Frédéric GUINAND
  • Yoann PIGNÉ
  • Eric SANLAVILLE (coord. local)
  • Mathilde VERNET (LIA)
IRIF, Université Paris Cité
  • Michel HABIB
  • Fabien de MONTGOLFIER
  • Reza NASERASR
  • Mikaël RABIE
  • Laurent VIENNOT (coord. local)

Abstract


Graphs are a fundamental modeling tool in science. They have been used for modeling phenomena in fields ranging from statistical physics to communication networks, distributed algorithms, logistics, biology, medicine, and social networks. Despite great successes in these areas, many real-world phenomena are dynamic and fall beyond the expressivity of standard graphs. In the past two decades, increasing interest has been devoted to temporal graphs (also called time-varying, time-dependent, evolving, or simply dynamic), in which the presence of edges and (sometimes) nodes depends on time. Early studies of temporal graphs occurred, independently, in each of the above fields. This led to a proliferation of new concepts and algorithmic questions, some of which are specific to a domain, while others are general, yet discovered independently and under various names. A temporal paths, which are paths that can be realized over time (along ascending labels), also known as time-respecting paths or journeys. The aim of our project is to develop a fundamental, i.e. domain-independent, theory of tempo- typical example is the one of ral graphs, with a focus on characterizing algorithmic problems and tools which are intrinsically temporal. The project has three main axes, which are (1) Classification of problems, (2) Tractability aspects, and (3) Algorithmic techniques.

Résumé


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.

Publications

Publications



La trame de ce site internet est inspirée d'une trame développée par Cyril Gavoille pour le projet ANR DESCARTES (2017-21).