Evènement pour le groupe Algorithmique Distribuée

Date 2013-02-18  14:00-15:00
TitreDistributed Calculation of Graph Diameter 
RésuméWe consider the problem of calculating the diameter of a graph given that there is a single vertex "Leader" and neighbouring vertices can exchange messages of a single bit at each round. We show that this can be achieved in the same O(n) time complexity as well known algorithms without this bound on message length. The techniques used can be applied to a number of other graph computations. We consider briefly how the algorithm behaves if applied in a situation where more than one vertex considers itself the Leader. Joint work with Yves Métivier and Akka Zemmari 
LieuSalle 178 
OrateurMike Robson (Labri) 

Aucun document lié à cet événement.

Retour à l'index