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é:   
Coloration distribuée et probabiliste
du groupe GT Graphes et Applications

Date 2014-07-11  14:00-15:00
TitreColoration distribuée et probabiliste 
RésuméLa coloration est un problème classique de la théorie des graphes et de l'algorithmique distribuée. Dans cet exposé, je ferai un résumé des résultats obtenus récemment pour la résolution de ce problème. On montrera comment obtenir une (Delta+1)-coloration en O(log n) rondes et en utilisant des messages à 1 bit. Nous montrerons que l'algorithme est optimal et ce en utilisant des revêtements de graphes. Dans le cas où le réseau est un anneau, nous verrons qu'en utilisant la transformée de Mellin, il est possible de donner la valeur exacte de la constante cachée dans le O(log n).  
LieuSalle 178 
OrateurAkka Zemmari 



Aucun document lié à cet événement.

Retour
Retour à l'index