Actualités
  Période
semaine
ou mois
aucune période


  Thèmes:
Thèses
Colloques
Autres
Groupes
Tous les thèmes

   
  Liens:
Voir les thèses

Voir les colloques

Voir les autres événements

Voir la page des groupes

Accéder à l'intranet

Intitulé:   
Algorithmes de mise à jour locale pour des graphes aléatoires
du 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