14:00
15:00

[gt.go] - "Un premier pas vers les graphes universels isométriques" by Edgar Baucher

/Exposé en français/Talk in french/

Les Graphes Universels Isométriques, qui vont de pair avec les Distance Labeling, peuvent être utilisés pour répondre à des questions d'optimisation de flux de données pour des algorithmes distribués, notamment lorsqu'on veut connaître la distance entre des sommets d'un graphe. Étant donné une famille de graphe F, un Graphe Universel Isométrique de F est un graphe qui contient tous les graphes de F en tant que sous-graphe isométrique, c'est à dire que pour tout graphe G de F, on peut retrouver G comme un sous-graphe du Graphe Universel Isométrique de F tel que toutes les distances entre les sommets de G sont les mêmes dans G et dans ce sous-graphe. L'objectif est en général de trouver le Graphe Universel Isométrique le plus petit (en terme de nombre de sommets) pour une famille donnée, ce qui laisse place à des problèmes allant de triviaux à NP-complets et de "amusant" à "à s'arracher les cheveux pour celles et ceux qui en ont encore".

Dans cet exposé, nous nous intéresserons à certaines propriétés structurelles et algorithmiques des Graphes Universels Isométriques. Ces graphes étant à ce jour très peu étudiés dans la recherche, nous nous intéresserons aussi aux liens qu'ils ont avec les Distance Labeling, qui sont eux plus étudiés.

[Edgar Baucher] (LaBRI )

[ https://www.labri.fr/perso/mbonamy | https://www.labri.fr/profil/Baucher_ID1671201662 ]

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

LaBRI/178