Bandeau du Laboratoire d'Informatique & Systèmes (LIS)

Soutenance de thèse de Sébastien RATEL

  • Date et heure: Vendredi 8 Novembre 2019 à 14h00
  • Lieu: Salle de séminaire du 2ème étage de la Frumam, St Charles
  • Titre: "Densité, VC-dimension et étiquetages de graphes"
  • Encadrants: Victor CHEPOI et Arnaud LABOUREL
Résumé
Un schéma d'étiquetage est un procédé permettant de distribuer la représentation d'un graphe sur ses sommets. Il consiste en une fonction d'encodage qui attribue des étiquettes binaires (courtes) à chaque sommet, et en une fonction de décodage qui, étant données les informations locales contenues dans deux étiquettes, et sans connaissance supplémentaire sur le graphe, permet de répondre (rapidement) à un type de requête pré-établi. Une partie des résultats de cette thèse sont initialement motivés par la construction de telles représentations distribuées. Ce document traite cependant de problèmes d'intérêt plus généraux tels que l'étude de bornes sur la densité de graphes, de la VC-dimension de familles d'ensembles, ou de propriétés métriques et structurelles. Nous établissons dans un premier temps des bornes supérieures sur la densité des sous-graphes de produits cartésien de graphes, puis des sous-graphes de demi-cubes. Pour ce faire, nous définissons des extensions du paramètre classique de VC-dimension (utilisé par Haussler, Littlestone et Warmuth en 1994 pour majorer la densité des sous-graphes d'hypercubes). De ces bornes sur la densité, nous déduisons des bornes supérieures sur la longueur des étiquettes attribuées par un schéma d'adjacence à ces familles de graphes. Dans un second temps, nous nous intéressons à des schémas de distance et de routage pour deux familles importantes de la théorie métrique des graphes: les graphes  médians et les graphes pontés. Nous montrons que la famille des graphes médians, sans cube, avec $n$ sommets, admet des schémas de distance et de routage utilisant tous deux des étiquettes de $O(\log^3 n)$. Ces étiquettes sont décodées en temps constant pour retourner, respectivement, la distance exacte entre deux sommets, ou le port vers un sommet rapprochant (strictement) une source d'une destination. Nous décrivons ensuite un schéma de distances $4$-approchées pour la famille des graphes pontés, sans $K_4$, avec $n$ sommets, utilisant des étiquettes de $O(\log^3 n)$ bits. Ces dernières peuvent être décodées en temps constant pour obtenir une  valeur entre la distance exacte et quatre fois celle-ci.
Jury
  • Nicolas NISSE, I3S/INRIA, Rapporteur
  • Laurent VIENNOT, IRIF/INRIA, Rapporteur
  • Olivier BOUSQUET, Google AI, Examinateur
  • Nadia CREIGNOU, LIS, Examinatrice
  • Cyril GAVOILLE, LaBRI, Examinateur
  • Nabil MUSTAFA, ESIEE, Examinateur
  • Victor CHEPOI, LIS, Directeur
  • Arnaud LABOUREL, LIS, Directeur