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

zbMATH Keywords

minimum spanning treedistributed computingbroadcast tree

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 7053292 (Why is no real title available?)
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A Fast Distributed Approximation Algorithm for Minimum Spanning Trees
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• A faster distributed protocol for constructing a minimum spanning tree
• A highly asynchronous minimum spanning tree protocol
• 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
• On the Complexity of Universal Leader Election
• Optimal distributed algorithm for minimum spanning trees revisited
• Time optimal self-stabilizing synchronization

Cited in

(4)

• Near-optimal distributed computation of small vertex cuts
• 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

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)