Reconstruction de graphes via des requêtes sur les triplets
Time: 14:00 -- Location: LRI, 445
summary: Considérons un oracle disposant d'un graphe labellisé caché. L'objectif de la reconstruction
de graphes est de retrouver ce graphe caché en interrogeant l'oracle avec certains types de requêtes.
Les requêtes que nous examinons portent sur des triplets de sommets du graphe, plus précisément, sur
la structure des graphes induits par ces triplets. Dans ce contexte, deux questions naturelles se posent.
Premièrement, quels sont les graphes que nous pouvons reconstruire ? Deuxièmement, s'il existe plusieurs
graphes qui répondent aux requêtes de la même manière, comment les énumérer efficacement ?
Pendant ce séminaire, je vais présenter le problème ainsi que deux des résultats que nous avons obtenus :
l'un sur la structure des graphes reconstructibles de manière unique, l'autre sur l’énumération efficace
des graphes cohérents avec les mêmes requêtes.
Ce travail a été réalisé pendant mon stage encadré par Hoang La, ainsi que mes co-auteurs : Florian Galliot, Matthieu Petiteau et Dimitri Watel.