Présentation:
On s'intéresse à la longueur du codage optimal de certaines familles de graphes, en particulier les arbres non dessinés à n sommets. Un codage pour une famille de graphes F_n à n sommets est une bijection (c'est-à-dire un algorithme de codage et un algorithme de décodage) qui à tout graphe G de F_n associe une chaîne binaire s(G). On note length(s(G)) sa longueur. s est assymptotiquement optimale pour F_n si pour tout G de F_n, length(s(G)) = (1+o(1))log₂(card(F_n)) où card(F_n) représente la cardinalité de F_n.

Le travail demandé sera dans une premier temps l'étude d'un article récent [1] permettant d'obtenir un codage optimal pour toute une catégorie de familles de graphes, dont celle des arbres non dessinés par un codage de longueur (1+o(1))cn bits pour une certaine constant c>0. Dans un deuxième temps il s'agira d'améliorer ce codage pour permettre de tester l'adjacence entre deux sommets en temps logarithmique (voir constant si possible), sans avoir à décoder complètement l'arbre. Il est bien clair qu'une telle recherche pourrait déboucher, si souhaité, sur une thèse.

Mots-clés: théorie des graphes, codage, algorithme, structures de données

Références:
1. SODA 2002