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é:   
About Lower Bounds on the Bit Complexity and the Execution Time of some Probabilistic Distributed Graph Algorithms
du groupe Algorithmique Distribuée

Date 2011-02-14  14:00-15:00
TitreAbout Lower Bounds on the Bit Complexity and the Execution Time of some Probabilistic Distributed Graph Algorithms  
RésuméWe present a general framework for proving lower bounds for the bit complexity (and thus the execution time) of some probabilistic distributed graph algorithms and we apply it to the complexity of some problems such as colouring, maximal matching or maximal independent set. We also give impossibility results on the existence of Las Vegas distributed algorithms to break symmetries at distance k for k >= 3. This is joint work with Y. Métivier, J.M. Robson and N. Saheb  
Lieus. 178 
OrateurAkka Zemmari 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index