A Distributed Algorithm for Constructing a Minimum Diameter Spanning Tree - Université Paris Nanterre Accéder directement au contenu
Article Dans Une Revue Journal of Parallel and Distributed Computing Année : 2004

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
Vignette du fichier
mdst04.pdf (525 Ko) Télécharger le fichier
Vignette du fichier
mdstenv.jpg (19.88 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Format : Figure, Image

Dates et versions

hal-00915195 , version 1 (06-12-2013)

Identifiants

Citer

Marc Bui, Franck Butelle, Christian Lavault. A Distributed Algorithm for Constructing a Minimum Diameter Spanning Tree. Journal of Parallel and Distributed Computing, 2004, 64 (5), pp.571--577. ⟨hal-00915195⟩
221 Consultations
177 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More