Evènement pour le groupe
Algorithmique Distribuée
Date | 2013-02-18 14:00-15:00 |
Titre | Distributed 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 |
Lieu | Salle 178 |
Orateur | Mike Robson (Labri) |
Url | Labri |
Aucun document lié à cet événement.
RetourRetour à l'index