Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
From MaRDI portal
Publication:1981632
DOI10.1007/s00446-020-00387-yOpenAlexW3126993486MaRDI QIDQ1981632
Publication date: 6 September 2021
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1806.04328
Related Items (2)
Latency, capacity, and distributed minimum spanning trees ⋮ Deterministic Fault-Tolerant Connectivity Labeling Scheme
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
- Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication
- An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
- A trade-off between information and communication in broadcast protocols
- Complexity of network synchronization
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
- An Optimal Synchronizer for the Hypercube
- Distributed Verification and Hardness of Distributed Approximation
- A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
- Distributed exact shortest paths in sublinear time
- A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities
- A highly asynchronous minimum spanning tree protocol
- Efficient threshold detection in a distributed environment
- Optimal distributed algorithm for minimum spanning trees revisited
- Fast distributed construction of k-dominating sets and applications
- On the Complexity of Universal Leader Election
- Dynamic graph connectivity in polylogarithmic worst case time
This page was built for publication: Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
