Evènement pour le groupe
GT Graphes et Applications
Date | 2014-02-07 14:00-15:00 |
Titre | Mise à 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. |
Lieu | Salle 178 |
Orateur | Romaric Duvignau |
Aucun document lié à cet événement.
RetourRetour à l'index