Latency, capacity, and distributed minimum spanning trees

DOI10.1016/j.jcss.2021.11.006zbMath1483.68248arXiv1902.08979OpenAlexW4200594446WikidataQ114162794 ScholiaQ114162794MaRDI QIDQ2119398

Peter Robinson, Suman Sourav, Fabian Kuhn, Seth Gilbert, John E. Augustine

Publication date: 29 March 2022

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1902.08979

zbMATH Keywords

capacitylatencyfragmentdistributed minimum spanning treeMST construction

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A faster distributed protocol for constructing a minimum spanning tree
• A fast distributed approximation algorithm for minimum spanning trees
• Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
• A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
• Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• Deterministic coin tossing with applications to optimal parallel list ranking
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Verification and Hardness of Distributed Approximation
• Distributed exact shortest paths in sublinear time
• A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities
• A highly asynchronous minimum spanning tree protocol
• Evaluating the running time of a communication round over the internet
• Round- and Message-Optimal Distributed Graph Algorithms
• On the Complexity of Universal Leader Election
• Distributed MST for constant diameter graphs
• Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history

This page was built for publication: Latency, capacity, and distributed minimum spanning trees