Evènement pour le groupe Séminaire Méthodes Formelles


Date 2017-12-05  11:00-12:00
TitreLa coloration de graphe dans le modèle LOCAL - Partie I 
RésuméL'objectif de cette série d'exposés est de faire découvrir un résultat aussi élégant que surprenant du calcul distribué, à savoir la 3-coloration des n-cycles en temps log*(n). On démontrera l'optimalité de ce résultat ainsi que ces généralisations au cas des graphes arbitraires. Partie I: - Le modèle LOCAL - Le problème de la coloration - Coloration des 1-orientations en 6 couleurs - De 6 à 3 couleurs - Cas des graphes arbitraires 
Lieu178 
OrateurCyril Gavoille 
Emailhttp://dept-info.labri.fr/~gavoille/ 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index