A Distributed Algorithm for Constructing a Minimum Diameter Spanning Tree

Abstract

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,ω)$. 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)$

Comments: 11 pages LaTeX, 2 figures; International Journal with referees article; New version (full paper design): results added in Section 2.2 and 2.2; typos removed