A Distributed Algorithm for Constructing a Minimum Diameter Spanning Tree
Bui, Marc · Butelle, Franck · Lavault, Christian
Distributed, Parallel, and Cluster Computing
Data Structures and Algorithms
Networking and Internet Architecture
68R10, 68W15, 05C85,
F.2.2; G.2.2; E.1; C.2.4
Original · EN
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 O(|V|) time complexity and O(|V||E|)
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.