Evènement pour le groupe Algorithmique Distribuée


Date 2016-05-30  14:00-15:00
TitreRandomized Distributed MIS and Colouring Algorithms for Rings with Oriented Edges in O(sqrt{log n}) bit rounds 
RésuméWe present and analyse Las Vegas distributed algorithms which compute a MIS or a colouring for anonymous rings with an arbitrary orientation of the edges; their bit complexity and time complexity are O(sqrt{log n}) with high probability. These algorithms are optimal modulo a multiplicative constant. Joint work with Yves Métivier and Mike Robson 
Lieu178 
OrateurAkka Zemmari 



Aucun document lié à cet événement.

Retour
Retour à l'index