A Distributed Algorithm for Constructing a Minimum Diameter Spanning Tree
Résumé
We present a new algorithm, which solves the problem of distributively finding a minimum diameter spanning tree of any (non-negatively) real-weighted graph $G = (V,E,\omega)$. As an intermediate step, we use a new, fast, linear-time all-pairs shortest paths distributed algorithm to find an absolute center of $G$. The resulting distributed algorithm is asynchronous, it works for named asynchronous arbitrary networks and achieves $\mathcal{O}(|V|)$ time complexity and $\mathcal{O}\left(|V|\,|E|\right)$
Fichier principal
mdst04.pdf (525 Ko)
Télécharger le fichier
mdstenv.jpg (19.88 Ko)
Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image