Evènement pour le 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