Evènement pour le groupe Algorithmique Distribuée


Date 2014-03-03  14:00-15:00
TitreAlgorithmes de mise à jour locale pour des graphes aléatoires 
RésuméAfin de modéliser l'évolution de réseaux logiques dynamiques, nous proposons de maintenir exactement une distribution donnée de graphes aléatoires lors d'une séquence arbitraire d'insertions et de suppressions de sommets. Nous nous plaçons dans un modèle local où nous n'avons pas accès à l'ensemble des sommets, mais supposons à la place l'accès à une primitive globale renvoyant un sommet aléatoire uniforme du graphe. Dans cet exposé, nous nous intéressons à maintenir la distribution uniforme dans les graphes k-sortants (graphes dirigés où tous les sommets ont degré sortant k). Nous présenterons plusieurs algorithmes d'insertion et de suppression pour le problème de maintenance, dont les plus efficaces sont asymptotiquement optimaux. 
Lieu178 
OrateurRomaric Duvignau  
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index