A highly asynchronous minimum spanning tree protocol

DOI10.1007/BF02242717MaRDI QIDQ5136990zbMATH OpenOpenAlexFDO

Authors Gurdip Singh, Arthur Bernstein

Publication date 30 November 2020

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02242717

zbMATH Keywords

graph theoryminimum spanning treedistributed algorithmssynchronizationtime complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Distributed algorithms (68W15)

Recommendations

• Improving the Time Complexity of Message-Optimal Distributed Algorithms for Minimum-Weight Spanning Trees
• A faster distributed protocol for constructing a minimum spanning tree
• A faster distributed protocol for constructing a minimum spanning tree
• Incremental distributed asynchronous algorithm for minimum spanning trees

Cited in

(12)

• Latency, capacity, and distributed minimum spanning trees
• Maintaining a dynamic set of processors in a distributed system
• A faster distributed protocol for constructing a minimum spanning tree
• Improving the Time Complexity of Message-Optimal Distributed Algorithms for Minimum-Weight Spanning Trees
• Optimal cost-sensitive distributed minimum spanning tree algorithm
• A New Proof of the GHS Minimum Spanning Tree Algorithm
• The multi-tree approach to reliability in distributed networks
• Distributed communication complexity of spanning tree construction
• A faster distributed protocol for constructing a minimum spanning tree
• Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
• Distributed MST and broadcast with fewer messages, and faster gossiping
• Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model

This page was built for publication: A highly asynchronous minimum spanning tree protocol

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