Projet de recherche doctoral numero :7049

Description

Date depot: 3 avril 2020
Titre: Problèmes d’énumération dans les graphes massifs et applications
Directrice de thèse: Clémence MAGNIEN (LIP6)
Directeur de thèse: Lionel TABOURIER (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Algorithmique, combinatoire

Resumé: Dans de nombreux contextes, des graphes sont étudiés : graphes du web, recommandation sur des réseaux sociaux, .... Il apparaît que les graphes rencontrés, issus du monde réel, ont une structure qui fait que de nombreux algorithmes sont très nettement plus rapides qu’attendu sur ces instances. Le projet vise à développer des algorithmes passant à l’échelle des graphes massifs extraits du monde réel, pour lesquels les besoins sont de plus en plus forts. Il se concentrera sur les problèmes d’énumération dans les graphes, c’est-à-dire les problèmes consistant à énumérer tous les éléments d’un certain ensemble défini à partir du graphe (comme par exemple énumérer toutes les cliques de taille 4, ou tous les motifs particuliers, d’un graphe). Le projet incorporera de plus une démarche interdisciplinaire afin d’appliquer les algorithmes développés à la biologie.



Doctorant.e: Baudin Alexis