A fast distributed approximation algorithm for minimum spanning trees
type: Item
instance of: scholarly article
title: A fast distributed approximation algorithm for minimum spanning trees
zbMATH Open document ID: 1266.68214
author: Maleq Khan
author: Gopal Pandurangan
published in: Distributed Computing
publication date: 2013-06-20T00:00:00Z
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6177666
zbMATH Keywords: minimum spanning tree
zbMATH Keywords: distributed approximation algorithm
zbMATH Keywords: randomized algorithm
MaRDI profile type: Publication
full work available at URL: s00446-007-0047-8
OpenAlex ID: W2058191123
cites work: Q3619797
cites work: Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
cites work: A Distributed Algorithm for Minimum-Weight Spanning Trees
cites work: A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
cites work: Dynamic analysis of the arrow distributed protocol
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Dynamic Steiner Tree Problem
cites work: A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms
cites work: The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
cites work: Optimal lower bounds for some distributed algorithms for a complete network of processors
cites work: Fast Distributed Construction of Smallk-Dominating Sets and Applications
cites work: Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
cites work: Distributed MST for constant diameter graphs
cites work: Distributed Computing: A Locality-Sensitive Approach
cites work: An Analysis of Several Heuristics for the Traveling Salesman Problem
cites work: Q4325545
DOI: 10.1007/S00446-007-0047-8
description: scientific article; zbMATH DE number 6177666