Evènement pour le groupe GT Graphes et Applications


Date 2014-01-17  14:00-15:00
TitreLe jeu de domination est P-Space log-complet 
RésuméDans cet exposé informel, nous (re-)découvrirons le jeu de domination et le paramètre associé, le nombre de domination ludique. Après avoir un peu présenté les avancées récentes sur le jeu, nous vérifierons une réduction du jeu (en espace logarithmique) vers un problème P-Space complet, montrant la complétude du jeu de domination. Il faut noter que, à ma connaissance, il n'existe pas encore de tel résultat pour la version classique du jeu de coloration et du nombre chromatique ludique.  
LieuSalle 178 
OrateurPaul Dorbec 



Aucun document lié à cet événement.

Retour
Retour à l'index