Evènement pour le groupe GT Graphes et Applications


Date 2014-02-07  14:00-15:00
TitreMise à jour locale de graphes aléatoires 
RésuméLes graphes k-sortants sont des graphes orientés dont chaque sommet possède exactement k voisins sortants. Nous étudions le problème de maintenir la distribution uniforme sur ces graphes lors d'une séquence arbitraire d'insertions et de suppressions de sommets. Le but étant de modéliser l'évolution de réseaux logiques dynamiques, nous nous plaçons dans un modèle local où nous n'avons pas accès à l'ensemble des sommets. Nous supposons à la place l'accès à une primitive globale renvoyant un sommet aléatoire uniforme du graphe. Nous présenterons dans cet exposé plusieurs algorithmes d'insertion et de suppression pour le problème de maintenance, dont les plus efficaces sont asymptotiquement optimaux.  
LieuSalle 178 
OrateurRomaric Duvignau 



Aucun document lié à cet événement.

Retour
Retour à l'index