A faster distributed protocol for constructing a minimum spanning tree

DOI10.1016/J.JCSS.2006.07.002MaRDI QIDQ856405zbMATH OpenOpenAlexFDO

Authors 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

minimum spanning treedistributed computing

Mathematics Subject Classification ID

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

Recommendations

• A faster distributed protocol for constructing a minimum spanning tree
• A fast distributed approximation algorithm for minimum spanning trees
• A Fast Distributed Approximation Algorithm for Minimum Spanning Trees
• A highly asynchronous minimum spanning tree protocol

Cites work

• scientific article; zbMATH DE number 432834 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Complexity of network synchronization
• Computing almost shortest paths (extended abstract)
• Distributed Computing: A Locality-Sensitive Approach
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• Fast distributed network decompositions and covers
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Locality in Distributed Graph Algorithms
• Optimal aggregation algorithms for middleware.
• Routing with Polynomial Communication-Space Trade-Off

Cited in

(16)

• On the microscopic view of time and messages
• Latency, capacity, and distributed minimum spanning trees
• A fast distributed approximation algorithm for minimum spanning trees
• scientific article; zbMATH DE number 2242700 (Why is no real title available?)
• How to use spanning trees to navigate in graphs
• A Fast Distributed Approximation Algorithm for Minimum Spanning Trees
• A highly asynchronous minimum spanning tree protocol
• On efficient distributed construction of near optimal routing schemes
• Faster Fully-Dynamic Minimum Spanning Forest
• scientific article; zbMATH DE number 1760042 (Why is no real title available?)
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• GHS algorithm on a graph with random weights
• Finding a small vertex cut on distributed networks
• A distributed algorithm for directed minimum-weight spanning tree
• A faster distributed protocol for constructing a minimum spanning tree
• Efficient minimum spanning tree algorithms on the reconfigurable mesh

This page was built for publication: A faster distributed protocol for constructing a minimum spanning tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q856405)