Les graphes de dimensions doublantes bornées ont été très étudiés récemment pour étendre des résultats connus dans les graphes Euclidiens : routage, calcul de distances, voyageur de commerce, ... et d'autres problèmes issus du calcul distribué.
Dans ce stage nous considérerons uniquement le problème du calcul de la distance à l'aide d'étiquette (distance labeling). Plus précisément, chaque sommet du graphe G doit recevoir une étiquette (binaire) telle que la distance dans le graphe entre les sommets x et y puisse être calculée à partir de leur étiquette L(x,G) et L(y,G), et de rien d'autre. Le but est de trouver un algorithme permettant d'affecter aux sommets des étiquettes de taille les plus courtes possibles.
Alors que la plupart des travaux concernent l'approximation de distance dans les graphes de dimension doublante bornée, il s'agira ici d'étudier le problème des distances extactes. Par exemple, en montrant que la largeur arborescente de ces graphes est sous-linéaire, il serait intéressant de prouver que les distances peuvent être calculées avec des étiquettes de taille sous-linéaire.
Mot-clés : théorie des graphes, algorithmes, dimension
doublante
Commentaires : Il est clair qu'un tel sujet peut déboucher sur
un sujet de thèse sur des problèmes connexes, notamment le candidat
pourra s'insérer éventuellement dans le projet ANR blanc <<
décomposition de graphes et algorithmes >> du LaBRI
(resp. B. Courcelle).
Références :
[GPPR] C. Gavoille, D. Peleg, S. Pérennès, et R. Raz.
Distance
Labeling in Graphs. Journal of Algorithms, 53:1, pp. 85-112,
2004.
[T] K. Talwar. Bypassing the Embedding: Algorithms for Low Dimensional Metrics. 36th Annual ACM Symposium on Theory of Computing (STOC). pp. 281-290, jun. 2004.
[GL] C. Gavoille, O. Ly. Distance Labeling in Hyperbolic Graphs. 16th Annual International Symposium on Algorithms and Computation (ISAAC). Vol. 3827 LNCS, pp. 1071-1079, dec. 2005.