A linear-time optimal-message distributed algorithm for minimum spanning trees

DOI10.1007/S00446-004-0107-2MaRDI QIDQ5138511zbMATH OpenOpenAlexFDO

Authors Michalis Faloutsos, Mart L. Molle

Publication date 4 December 2020

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00446-004-0107-2

zbMATH Keywords

minimum spanning treeoptimal timetime complexity

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 749815
• Improving the Time Complexity of Message-Optimal Distributed Algorithms for Minimum-Weight Spanning Trees
• A Fast Distributed Approximation Algorithm for Minimum Spanning Trees
• A fast distributed approximation algorithm for minimum spanning trees
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• A distributed approximation algorithm for the minimum degree minimum weight spanning trees
• A distributed algorithm for constructing a minimum diameter spanning tree

Cites work

• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Fast distributed construction of k-dominating sets and applications
• Optimal distributed algorithm for minimum spanning trees revisited

Cited in

(5)

• Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
• A Class of Optimal Structures for Node Computations in Message Passing Algorithms
• Distributed MST and broadcast with fewer messages, and faster gossiping
• An ‘All pairs shortest paths’ distributed algorithm using 2n 2 messages

This page was built for publication: A linear-time optimal-message distributed algorithm for minimum spanning trees

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