Distributed MST and broadcast with fewer messages, and faster gossiping
From MaRDI portal
Publication:5090922
DOI10.4230/LIPICS.DISC.2018.30zbMATH Open1497.68564MaRDI QIDQ5090922FDOQ5090922
Authors: Mohsen Ghaffari, Fabian Kuhn 
Publication date: 21 July 2022
Recommendations
- A simple deterministic distributed MST algorithm, with near-optimal time and message complexities
- A simple deterministic distributed MST algorithm, with near-optimal time and message complexities
- A time- and message-optimal distributed algorithm for minimum spanning trees
- A time- and message-optimal distributed algorithm for minimum spanning trees
- Round- and message-optimal distributed graph algorithms
Cites Work
- Distributed minimum cut approximation
- Distributed Computing: A Locality-Sensitive Approach
- Distributed approximation algorithms for weighted shortest paths
- Fast routing table construction using small messages (extended abstract)
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- Distributed verification and hardness of distributed approximation
- Near-optimal distributed approximation of minimum-weight connected dominating set
- Tight bounds for distributed MST verification
- Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history
- Tight bounds for rumor spreading in graphs of a given conductance
- Fast distributed construction of k-dominating sets and applications
- A fast distributed approximation algorithm for minimum spanning trees
- Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- Distributed MST and routing in almost mixing time
- Toward optimal bounds in the congested clique, graph connectivity and MST
- Simple, fast and deterministic gossip and rumor spreading
- Almost-Tight Distributed Minimum Cut Algorithms
- On the Complexity of Universal Leader Election
- Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication
- A time- and message-optimal distributed algorithm for minimum spanning trees
- A simple deterministic distributed MST algorithm, with near-optimal time and message complexities
- A highly asynchronous minimum spanning tree protocol
- A linear-time optimal-message distributed algorithm for minimum spanning trees
- Distributed algorithms for planar networks. II: Low-congestion shortcuts, MST, and Min-Cut
- MST in \(O(1)\) rounds of congested clique
- MST in log-star rounds of congested clique
- Near-optimal distributed maximum flow (extended abstract)
Cited In (14)
- Fast gossiping on mesh-bus computers
- Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication
- Low-congestion shortcut and graph parameters
- Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits
- Latency, capacity, and distributed minimum spanning trees
- Communication costs in a geometric communication network
- Deterministic Fault-Tolerant Connectivity Labeling Scheme
- Round- and message-optimal distributed graph algorithms
- Communication efficient self-stabilizing leader election
- On further reducing the cost of parallel pipelined message broadcasts
- A simple deterministic distributed MST algorithm, with near-optimal time and message complexities
- Time-message trade-offs in distributed algorithms
- Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
- Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
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)
