Formation doctorale Informatique
Proposition de sujet thèse
Sujet : Représentation efficace des graphes
Responsable : Cyril Gavoille
Téléphone : 05.56.84.69.16
e-mail : gavoille@labri.fr
Site Web : http://dept-info.labri.fr/~gavoille
Equipe : Combinatoire et Algorithmique : Graphes & Applications
Présentation du sujet :
Les graphes sont des objets combinatoires couramment utilisés comme
support et la modélisation de nombreux problèmes algorithmiques.
La question abordée dans cette thèse est la représentation << efficace >>
des graphes en mémoire. Par exemple, les entrepôts de données sont
couramment structurés sur le Web par de très grands fichiers de tags XML,
fichiers représentés par des arbres et permettant des requêtes.
Plus précisemment, on s'intéresse à la longueur du codage optimal de
certaines familles de graphes, par exemple les arbres non dessinés à
n sommets. Un codage pour une famille de graphes Fn à n sommets
est une bijection (c'est-à-dire un algorithme de codage et un algorithme
de décodage) qui à tout graphe G de Fn associe une chaîne binaire s(G).
On note length(s(G)) sa longueur. Le codage s est assymptotiquement
optimale pour Fn si pour tout G de Fn, length(s(G)) = (1+o(1))log2(card(Fn))
où card(Fn) représente la cardinalité de Fn.
Le codage optimal pour certaines familles est connue (voir [1] par exemple).
Cependant, dans la pratique, on souhaite un codage non seulement
compact, mais aussi efficace pour permettre de répondre à certaines
requêtes en temps constant où en temps O(logn): adjacence ou distance entre
deux sommets, calcul du plus proche ancêtre commun dans un arbre, etc.,
cf. [2].
Une partie du travail sera de proposer de nouveaux algorithmes de
codages optimaux supportant des requêtes.
Mot-clés : théorie des graphes, codage, algorithme, structures de données
Références :
[1] SODA 2002
[2] D. Harel and R. E. Tarjan, Fast algorithms for finding nearest
common ancestors, SIAM Journal on Computing, 13 (1984), pp. 338-355.