A fast distributed approximation algorithm for minimum spanning trees

DOI10.1007/S00446-007-0047-8MaRDI QIDQ1954259zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

minimum spanning treerandomized algorithmdistributed approximation algorithm

Mathematics Subject Classification ID

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

Recommendations

• A Fast Distributed Approximation 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

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 732976 (Why is no real title available?)
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Distributed Computing: A Locality-Sensitive Approach
• Distributed MST for constant diameter graphs
• Dynamic Steiner Tree Problem
• Dynamic analysis of the arrow distributed protocol
• Fast Distributed Construction of Smallk-Dominating Sets and Applications
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• Probability Inequalities for Sums of Bounded Random Variables
• 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

Cited in

(25)

• A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
• Computing and Combinatorics
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
• scientific article; zbMATH DE number 1304097 (Why is no real title available?)
• 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
• A faster distributed protocol for constructing a minimum spanning tree
• Brief announcement: Distributed approximation for tree augmentation
• scientific article; zbMATH DE number 1756011 (Why is no real title available?)
• Efficient distributed computation of distance sketches in networks
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• 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
• Faster Fully-Dynamic Minimum Spanning Forest
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• Distributed graph algorithms and their complexity: an introduction
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• A Local Distributed Algorithm to Approximate MST in Unit Disc Graphs
• A faster distributed protocol for constructing a minimum spanning tree
• Distributed MST and broadcast with fewer messages, and faster gossiping
• 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)