Evènement pour le groupe Algorithmique Distribuée


Date 2015-05-11  14:00-15:00
TitreCalculer les distances dans un graphe en temps constant avec des étiquettes de 0.793n bits 
RésuméDans cet exposé je présenterai une structure de données compacte permettant de calculer en temps constant la distance entre n'importe quelle paire de sommets d'un graphe arbitraire à n sommets. Cette structure de données se présente sous forme d'étiquette associée à chacun des sommets, la distance entre les u et v étant décodée à partir d'un calcul impliquant seulement les étiquettes de u et de v. La solution triviale, à l'aide d'un vecteur de distances de taille n, produit des étiquettes de nlogn bits. En fait, aucune technique utilisant o(nlogn) bits et décodant en temps constant n'est connue. Cependant, si on relâche la contrainte du décodage en temps constant, des solutions avec O(n) bits existent. Une des meilleures d'entres elles utilisent 11n bits pour un décodage O(logn). Notre solution réduit la taille des étiquettes à 0.793n bits avec un décodage constant et s'étend naturellement aux graphes valués.  
Lieu178 
OrateurCyril Gavoille 



Aucun document lié à cet événement.

Retour
Retour à l'index