Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model
From MaRDI portal
Publication:5090930
DOI10.4230/LIPICS.DISC.2018.37zbMATH Open1497.68567MaRDI QIDQ5090930FDOQ5090930
Authors: Ali Mashreghi, Valerie King 
Publication date: 21 July 2022
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
Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Distributed algorithms (68W15)
Cites Work
- A trade-off between information and communication in broadcast protocols
- Distributed verification and hardness of distributed approximation
- Time optimal self-stabilizing synchronization
- Complexity of network synchronization
- 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
- A Fast Distributed Approximation Algorithm for Minimum Spanning Trees
- Dynamic graph connectivity in polylogarithmic worst case time
- Efficient threshold detection in a distributed environment (extended abstract)
- A faster distributed protocol for constructing a minimum spanning tree
- Optimal distributed algorithm for minimum spanning trees revisited
- Title not available (Why is that?)
- An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
- On the Complexity of Universal Leader Election
- Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication
- A highly asynchronous minimum spanning tree protocol
Cited In (4)
- Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication
- Near-optimal distributed computation of small vertex cuts
- Communication costs in a geometric communication network
- Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
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)
