Reconstruction de graphes par oracle de distance
Time: 15:00 -- Location: bat 650, 445
summary: Étant donné un graphe connexe G = (V,E) où les sommets sont connus et les arêtes sont cachées, nous avons accès à un oracle capable de répondre aux requêtes suivantes : étant donné deux sommets u et v dans V, l'oracle retourne la distance d'un plus court chemin entre u et v dans G. Ce problème apparait naturellement dans des questions de reconstruction de réseau informatique ou d'arbre phylogénétique. Cette présentation explore ce qui est connu sur le nombre de requêtes nécessaire pour reconstruire diverses classes de graphes, ainsi que les développements récents concernant la principale conjecture ouverte dans le domaine : est-il possible de reconstruire les graphes de degré borné en utilisant un nombre de requêtes quasi-linaire en la taille de V ?