A fast distributed approximation algorithm for minimum spanning trees
From MaRDI portal
Publication:1954259
DOI10.1007/S00446-007-0047-8zbMATH Open1266.68214OpenAlexW2058191123MaRDI QIDQ1954259FDOQ1954259
Authors: Maleq Khan, Gopal Pandurangan 
Publication date: 20 June 2013
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-007-0047-8
Recommendations
- A Fast Distributed Approximation Algorithm for Minimum Spanning Trees
- A time- and message-optimal distributed algorithm for minimum spanning trees
- A time- and message-optimal distributed algorithm for minimum spanning trees
- A faster distributed protocol for constructing a minimum spanning tree
- A faster distributed protocol for constructing a minimum spanning tree
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Distributed algorithms (68W15)
Cites Work
- Probability Inequalities for Sums of Bounded Random Variables
- Title not available (Why is that?)
- An Analysis of Several Heuristics for the Traveling Salesman Problem
- Distributed Computing: A Locality-Sensitive Approach
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- Dynamic Steiner Tree Problem
- Distributed MST for constant diameter graphs
- Title not available (Why is that?)
- Fast Distributed Construction of Smallk-Dominating Sets and Applications
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
- Dynamic analysis of the arrow distributed protocol
- Optimal lower bounds for some distributed algorithms for a complete network of processors
- The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
- Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
- A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms
Cited In (21)
- Computing and Combinatorics
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
- Title not available (Why is that?)
- Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
- Latency, capacity, and distributed minimum spanning trees
- Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
- Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE
- A faster distributed protocol for constructing a minimum spanning tree
- Distributed Graph Algorithms and their Complexity: An Introduction
- Title not available (Why is that?)
- Efficient distributed computation of distance sketches in networks
- Low-congestion shortcuts without embedding
- A Fast Distributed Approximation Algorithm for Minimum Spanning Trees
- A linear-time optimal-message distributed algorithm for minimum spanning trees
- Title not available (Why is that?)
- Faster Fully-Dynamic Minimum Spanning Forest
- Efficient distributed approximation algorithms via probabilistic tree embeddings
- A Local Distributed Algorithm to Approximate MST in Unit Disc Graphs
- A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
- A fast minimum spanning tree algorithm based on \(K\)-means
This page was built for publication: A fast distributed approximation algorithm for minimum spanning trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1954259)
