Proposition de projet TER

• Titre du Sujet:

  Compression d'adresses dans les réseaux arborescents

  
  
  

• Nom du responsables

  Cyril Gavoille

  
  
  

• Adresse, Tél, mail:

  LaBRI,
  Université Bordeaux I, bât. A30
  351, cours de la Libération,
  33405 Talence cedex

  Bureau: 210
  Tél: 05.56.84.88.12
  E-mail: gavoille@labri.fr
  Web: http://dept-info.labri.fr/~gavoille

  
  
  

• Description du travail souhaité:

  Dans un article récent [1], il est montré qu'il est possible d'affecter à chaque sommet d'un arbre une étiquette (ou adresse) de sorte qu'il soit possible de déterminer si deux sommets dans l'arbre sont voisins à partir de leur adresses, sans qu'aucune connaissance globale ne soit requise. Dans [1] il est fourni une technique produisant des adresses de log₂n+O(log^*n) bits où n est le nombre de sommets de l'arbre.

  Dans ce stage, il s'agira d'étudier, puis d'implémenter (éventuellement d'améliorer) l'algorithme donné en [1], afin de pouvoir étudier expérimentalement la longueur des adresses générées. Il s'agira, par exemple, de confronter l'expérimentation à la complexité théorique annoncée dans l'article. On pourra donner, par exemple, le maximum du nombre de sommets d'un arbre que l'on peut étiquetter de cette manière si les adresses sont codées sur 32 bits au plus.

  
  
  

• Moyens matériels et logiciels nécessaires:

  Porgrammation C.

  
  
  

• Références Bibliographiques et Http: :

  [1] Stephen Alstrup et Theis Rauhe. Small Induced-Universal Graphs and Compact Implicit Graph Representations. FOCS '02.