A fast distributed approximation algorithm for minimum spanning trees

DOI10.1007/s00446-007-0047-8zbMath1266.68214OpenAlexW2058191123MaRDI QIDQ1954259

Gopal Pandurangan, Maleq Khan

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

zbMATH Keywords

randomized algorithmminimum spanning treedistributed approximation algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (11)

Latency, capacity, and distributed minimum spanning trees ⋮ Low-congestion shortcuts without embedding ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ A fast minimum spanning tree algorithm based on \(K\)-means ⋮ Unnamed Item ⋮ Efficient distributed approximation algorithms via probabilistic tree embeddings ⋮ Efficient distributed computation of distance sketches in networks ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Distributed Approximation Algorithms for Steiner Tree in the CONGESTED CLIQUE ⋮ Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time

Cites Work

• Dynamic analysis of the arrow distributed protocol
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms
• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
• The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Dynamic Steiner Tree Problem
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Distributed Computing: A Locality-Sensitive Approach
• Probability Inequalities for Sums of Bounded Random Variables
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Distributed MST for constant diameter graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: A fast distributed approximation algorithm for minimum spanning trees