Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model

DOI10.4230/LIPICS.DISC.2018.37MaRDI QIDQ5090930zbMATH OpenFDO

Authors Ali Mashreghi, Valerie King

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2018.37

zbMATH Keywords

broadcast treedistributed computingminimum spanning tree

Mathematics Subject Classification ID

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

Recommendations

• Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
• Construction and impromptu repair of an MST in a distributed network with o(m) communication
• Distributed MST and broadcast with fewer messages, and faster gossiping
• A highly asynchronous minimum spanning tree protocol

Cites work

• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A Fast Distributed Approximation Algorithm for Minimum Spanning Trees
• A faster distributed protocol for constructing a minimum spanning tree
• A highly asynchronous minimum spanning tree protocol
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• A trade-off between information and communication in broadcast protocols
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• Complexity of network synchronization
• Construction and impromptu repair of an MST in a distributed network with o(m) communication
• Distributed verification and hardness of distributed approximation
• Dynamic graph connectivity in polylogarithmic worst case time
• Efficient threshold detection in a distributed environment (extended abstract)
• Fast distributed construction of k-dominating sets and applications
• scientific article; zbMATH DE number 7053292 (Why is no real title available?)
• On the Complexity of Universal Leader Election
• Optimal distributed algorithm for minimum spanning trees revisited
• Time optimal self-stabilizing synchronization

Cited in

(4)

• Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
• Construction and impromptu repair of an MST in a distributed network with o(m) communication
• Communication costs in a geometric communication network
• Near-optimal distributed computation of small vertex cuts

This page was built for publication: Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model

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