DIDYA – Algorithmes de graphes distribués dynamiques

Ce projet de recherche porte sur un sujet d'importance à la fois théorique et pratique : les algorithmes de graphes à la fois distribués et dynamiques. Une longue série de travaux sur les algorithmes de graphes distribués étudie la résolution de problèmes sur des graphes statiques, par exemple la construction d'un arbre couvrant ou d'une coloration des sommets. La théorie des algorithmes de graphes dynamiques étudie quant à elle des structures de données permettant de maintenir des constructions similaires dans des graphes qui évoluent avec le temps, mais de manière centralisée. Notre but est de développer une théorie des algorithmes ayant les deux caractéristiques à la fois : être distribué et être utilisable dans un contexte dynamique.