Direction de recherche : Lionel TABOURIER

Co-encadrement : Clémence Magnien

Ordonner les nœuds pour passer à l'échelle sur les grands graphes réels

Les graphes peuvent décrire de nombreuses situations du monde réel telles que le réseau internet, les échanges commerciaux et les citations scientifiques. La taille des graphes disponibles augmente rapidement, ce qui nécessite des algorithmes rapides et qui passent à l'échelle.
Pour atteindre ce but, l'une des techniques clefs est d'ordonner les nœuds en fonction de certaines propriétés, telles que le degré ou la centralité. Cette approche est utilisée dans les méthodes les plus performantes pour plusieurs problèmes liés aux graphes : la gestion de la mémoire cache, la compression ou la recherche de motifs.
Cette thèse présente de nouvelles contributions basées sur l'ordre des nœuds. Tout d'abord, nous analysons la complexité d'un algorithme de listage de triangles et proposons de nouveaux ordres qui la réduisent et accélèrent le processus de listage. Ensuite, nous montrons comment des ordres simples peuvent améliorer les garanties de couverture par sommets sans compromettre la rapidité.

Publications 2021-2024