A time- and message-optimal distributed algorithm for minimum spanning trees [PDF]
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017 This article presents a randomized (Las Vegas) distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in Õ( D + √ n ) time and exchanges Õ( m
Gopal Pandurangan +2 more
openalex +6 more sources
A Surprisingly Simple Method for Distributed Euclidean-Minimum Spanning Tree / Single Linkage Dendrogram Construction from High Dimensional Embeddings via Distance Decomposition [PDF]
arXiv.orgWe introduce a decomposition method for the distributed calculation of exact Euclidean Minimum Spanning Trees in high dimensions (where sub-quadratic algorithms are not effective), or more generalized geometric-minimum spanning trees of complete graphs ...
Richard Lettich
openalex +2 more sources
Distributed Algorithms for Minimum Degree Spanning Trees
, 2018 The minimum degree spanning tree (MDST) problem requires the construction of a spanning tree $T$ for graph $G=(V,E)$ with $n$ vertices, such that the maximum degree $d$ of $T$ is the smallest among all spanning trees of $G$. In this paper, we present two new distributed approximation algorithms for the MDST problem.
Michael Dinitz +2 more
openalex +4 more sources
Distributed coordinated motion control of multiple UAVs oriented to optimization of air-ground relay network [PDF]
Scientific ReportsA novel adaptive model-based motion control method for multi-UAV communication relay is proposed, which aims at improving the networks connectivity and the communications performance among a fleet of ground unmanned vehicles.
Cancan Tao, Bowen Liu
doaj +2 more sources
A Distributed Parallel Algorithm for the Minimum Spanning Tree Problem [PDF]
arXiv.org, 2017 In this paper, we present and evaluate a parallel algorithm for solving the minimum spanning tree (MST) problem on supercomputers with distributed memory. The algorithm relies on the relaxation of the message processing order requirement for one specific message type compared to the original GHS (Gallager, Humblet, Spira) algorithm.
Alexander Semenov +2 more
openaire +3 more sources
THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS [PDF]
International Journal of Foundations of Computer Science, 2004 In this paper we present the first distributed algorithm on general graphs for the Minimum Degree Spanning Tree problem. The problem is NP-hard in sequential. Our algorithm give a Spanning Tree of a degree at most 1 from the optimal. The resulting distributed algorithm is asynchronous, it works for named asynchronous arbitrary networks and achieves O(
Lélia Blin, Franck Butelle
openalex +7 more sources
Fully Sequential and Distributed Dynamic Algorithms for Minimum Spanning Trees
, 2000 In this paper, we present a fully-dynamic distributed algorithm for maintaining a minimum spanning tree on general graphs with positive real edge weights. The goal of a dynamic MST algorithm is to update efficiently the minimum spanning tree after dynamic changes like edge weight changes, rather than having to recompute it from scatch each time.
P. Mohapatra
openalex +4 more sources
Note on distributed certification of minimum spanning trees
, 2019 A note explaining a known result. (New version, with minor changes.)
Laurent Feuilloley
openalex +4 more sources
A Distributed Parallel Algorithm for Minimum Spanning Tree Problem
, 2016 11 pages, 5 figures, 2 ...
Artem Mazeev +2 more
openalex +4 more sources
A Distributed Algorithm for Minimum-Weight Spanning Trees [PDF]
ACM Transactions on Programming Languages and Systems, 1983 Robert G. Gallager +2 more
openalex +4 more sources