A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
From MaRDI portal
Recommendations
Cited in
(43)- A distributed algorithm for k-dominating sets
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- Fast distributed approximation for TAP and 2-edge-connectivity
- Graph spanners: a tutorial review
- On the microscopic view of time and messages
- Universally optimal information dissemination and shortest paths in the HYBRID distributed model
- Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Low-congestion shortcut and graph parameters
- Latency, capacity, and distributed minimum spanning trees
- Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
- Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
- A distributed approximation algorithm for the minimum degree minimum weight spanning trees
- A fast distributed approximation algorithm for minimum spanning trees
- Exact bounds for distributed graph colouring
- scientific article; zbMATH DE number 2088672 (Why is no real title available?)
- A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
- Distributed MST for constant diameter graphs
- A distributed algorithm for directed minimum-weight spanning tree
- Networks cannot compute their diameter in sublinear time
- Sparsifying congested cliques and core-periphery networks
- Minimum-weight spanning tree algorithms. A survey and empirical study
- Low-congestion shortcuts without embedding
- Sublinear fully distributed partition with applications
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
- Labeling schemes for tree representation
- Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time
- From sequential layers to distributed processes
- Deterministic distributed construction of T-dominating sets in time T
- A linear-time optimal-message distributed algorithm for minimum spanning trees
- Time optimal algorithms for black hole search in rings
- On efficient distributed construction of near optimal routing schemes
- Distributed graph algorithms and their complexity: an introduction
- Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
- A distributed algorithm to find \(k\)-dominating sets
- Finding a small vertex cut on distributed networks
- THE FIRST APPROXIMATED DISTRIBUTED ALGORITHM FOR THE MINIMUM DEGREE SPANNING TREE PROBLEM ON GENERAL GRAPHS
- A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms
- Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
- Fast distributed approximation for TAP and 2-edge-connectivity
- A distributed algorithm for constructing a minimum diameter spanning tree
- Time-message trade-offs in distributed algorithms
- Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
This page was built for publication: A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4388873)
