A faster distributed protocol for constructing a minimum spanning tree

DOI10.1016/J.JCSS.2006.07.002zbMATH Open1118.68026OpenAlexW2030982625MaRDI QIDQ856405FDOQ856405

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

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 time- and message-optimal distributed algorithm for minimum spanning trees
• A highly asynchronous minimum spanning tree protocol

zbMATH Keywords

minimum spanning treedistributed computing

Mathematics Subject Classification ID

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

Cites Work

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

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
• Title not available (Why is that?)
• 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
• Faster Fully-Dynamic Minimum Spanning Forest
• On efficient distributed construction of near optimal routing schemes
• Title not available (Why is that?)
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• Finding a small vertex cut on distributed networks
• GHS algorithm on a graph with random weights
• 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)