A faster distributed protocol for constructing a minimum spanning tree

DOI10.1016/j.jcss.2006.07.002zbMath1118.68026OpenAlexW2030982625MaRDI QIDQ856405

Michael Elkin

Publication date: 7 December 2006

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

Full work available at URL: https://doi.org/10.1016/j.jcss.2006.07.002

zbMATH Keywords

distributed computingminimum spanning tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Network protocols (68M12)

Related Items

Latency, capacity, and distributed minimum spanning trees, How to use spanning trees to navigate in graphs, GHS algorithm on a graph with random weights, A distributed algorithm for directed minimum-weight spanning tree, On efficient distributed construction of near optimal routing schemes, On the Microscopic View of Time and Messages, Efficient distributed approximation algorithms via probabilistic tree embeddings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast distributed network decompositions and covers
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Optimal aggregation algorithms for middleware.
• Complexity of network synchronization
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Locality in Distributed Graph Algorithms
• Routing with Polynomial Communication-Space Trade-Off
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• Distributed Computing: A Locality-Sensitive Approach
• Computing almost shortest paths