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