Evènement pour le groupe Combinatoire Énumérative et Algébrique


Date 2012-01-06  10:45-11:45
TitreComplexité de la coloration probabiliste d'un anneau : une application de la transformée de Mellin 
RésuméDans cet exposé, on s'intéresse à la 3-coloration distribuée d'un anneau anonyme. Nous étudions la complexité en temps et la bit-complexité de ce problème en présentant un algorithme probabiliste permettant de le résoudre et en montrant une borne inférieure générale. L'analyse de l'algorithme utilise la transformée de Mellin, ce qui permet de donner la valeur exacte du temps moyen et non seulement une borne supérieure. Nous en déduisons que l'algorithme présenté est optimal. Travail en collaboration avec Y. Métivier, M. Robson et N. Saheb. 
Lieu076 
OrateurAkka Zemmari  



Aucun document lié à cet événement.

Retour
Retour à l'index