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