Affordable Access

Densité, VC-dimension et étiquetages de graphes

Authors
  • Ratel, Sébastien
Publication Date
Nov 08, 2019
Source
Kaleidoscope Open Archive
Keywords
Language
French
License
Unknown
External links

Abstract

Un schéma d’étiquetage est un procédé permettant de distribuer la représentationd’un graphe sur ses sommets. Il consiste en une fonction d’encodage quiattribue des étiquettes binaires (courtes) à chaque sommet, et d’une fonction dedé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 cettethè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 telsque l’étude de bornes sur la densité de graphes, de la VC-dimension de famillesd’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-graphesde demi-cubes. Pour ce faire, nous définissons des extensions du paramètre classiquede VC-dimension (utilisé par Haussler, Littlestone et Warmuth en 1994pour majorer la densité des sous-graphes d’hypercube). De ces bornes sur ladensité, nous déduisons des bornes supérieures sur la longueur des étiquettesattribuées par un schéma d’adjacence à ces deux familles de graphes.Dans un second temps, nous nous intéressons à des schémas de distance etde 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 graphesmédians, sans cube, avec n sommets, admet des schémas de distance et deroutage utilisant tous deux des étiquettes de O(log^3 n). Ces étiquettes sont décodéesen temps constant pour retourner, respectivement, la distance exacte entredeux sommets, ou le port vers un sommet rapprochant (strictement) une sourced’une destination. Nous décrivons ensuite un schéma de distance 4-approchépour la famille des graphes pontés, sans K_4, avec n sommets, utilisant des étiquettesde O(log^3 n) bits. Ces dernières peuvent être décodées en temps constantpour obtenir une valeur entre la distance exacte et quatre fois celle-ci.

Report this publication

Statistics

Seen <100 times