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é:   
A Distributed Enumeration Algorithm and Applications to All Pairs Shortest Paths, Diameter...
du groupe Algorithmique Distribuée

Date 2015-02-09  14:00-15:00
TitreA Distributed Enumeration Algorithm and Applications to All Pairs Shortest Paths, Diameter... 
RésuméWe consider the standard message passing model; we assume the system is fully synchronous: all processes start at the same time and time proceeds in synchronised rounds. In each round each vertex can transmit a different message of size $O(1)$ to each of its neighbours. This paper proposes and analyses a distributed enumeration algorithm of vertices of a graph having a distinguished vertex which satisfies that two vertices with consecutive numbers are at distance at most $3$. We prove that its time complexity is $O(n)$ where $n$ is the number of vertices of the graph. Furthermore, the size of each message is $O(1)$ thus its bit complexity is also $O(n).$ We provide some links between this enumeration and Hamiltonian graphs from which we deduce that this enumeration is optimal in the sense that there does not exist an enumeration which satisfies that two vertices with consecutive numbers are at distance at most $2$. We deduce from this enumeration algorithms which compute all pairs shortest paths and the diameter with a time complexity and a bit complexity equal to $O(n)$. This improves the best known distributed algorithms (under the same hypotheses) for computing all pairs shortest paths or the diameter presented in cite{PRT12,HW12} having a time complexity equal to $O(n)$ and which use messages of size $O(log n)$ bits. Join work with Mike Robson and Akka Zemmari 
Lieu178 
OrateurYves Métivier 



Aucun document lié à cet événement.

Retour
Retour à l'index