Distributed MST and broadcast with fewer messages, and faster gossiping
From MaRDI portal
Publication:5090922
Recommendations
Cites work
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- A fast distributed approximation algorithm for minimum spanning trees
- A highly asynchronous minimum spanning tree protocol
- A linear-time optimal-message distributed algorithm for minimum spanning trees
- Almost-Tight Distributed Minimum Cut Algorithms
- Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication
- Distributed Computing: A Locality-Sensitive Approach
- Distributed MST and routing in almost mixing time
- Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
- Distributed approximation algorithms for weighted shortest paths
- Distributed minimum cut approximation
- Distributed verification and hardness of distributed approximation
- Fast distributed construction of k-dominating sets and applications
- Fast routing table construction using small messages (extended abstract)
- MST in \(O(1)\) rounds of congested clique
- MST in log-star rounds of congested clique
- Near-optimal distributed approximation of minimum-weight connected dominating set
- Near-optimal distributed maximum flow (extended abstract)
- On the Complexity of Universal Leader Election
- Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history
- Simple, fast and deterministic gossip and rumor spreading
- Tight bounds for rumor spreading in graphs of a given conductance
- Toward optimal bounds in the congested clique, graph connectivity and MST
- Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
Cited in
(14)- Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits
- Fast gossiping on mesh-bus computers
- Latency, capacity, and distributed minimum spanning trees
- Round- and message-optimal distributed graph algorithms
- On further reducing the cost of parallel pipelined message broadcasts
- Deterministic Fault-Tolerant Connectivity Labeling Scheme
- Time-message trade-offs in distributed algorithms
- scientific article; zbMATH DE number 1202979 (Why is no real title available?)
- Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
- Communication efficient self-stabilizing leader election
- 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
- Low-congestion shortcut and graph parameters
This page was built for publication: Distributed MST and broadcast with fewer messages, and faster gossiping
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090922)
