A Fast Distributed Approximation Algorithm for Minimum Spanning Trees

DOI10.1007/11864219_25MaRDI QIDQ3524318zbMATH OpenOpenAlexFDO

Authors Maleq Khan, Gopal Pandurangan

Publication date 9 September 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11864219_25

zbMATH Keywords

minimum spanning treedistributed 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

Cited in

(22)

• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• Distributed Minimum Degree Spanning Trees
• A fast distributed approximation algorithm for minimum spanning trees
• A distributed approximation algorithm for the minimum degree minimum weight spanning trees
• Brief announcement: Distributed approximation for tree augmentation
• scientific article; zbMATH DE number 1756011 (Why is no real title available?)
• A Local Distributed Algorithm to Approximate MST in Unit Disc Graphs
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• Distributed algorithms for low stretch spanning trees
• A linear-time optimal-message distributed algorithm for minimum spanning trees
• A faster distributed protocol for constructing a minimum spanning tree
• Computing and Combinatorics
• Energy-efficient cooperative data aggregation for wireless sensor networks
• Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
• A faster distributed protocol for constructing a minimum spanning tree
• Faster Fully-Dynamic Minimum Spanning Forest
• Distributed approximation of minimum routing cost trees
• Silent MST Approximation for Tiny Memory
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
• scientific article; zbMATH DE number 1304097 (Why is no real title available?)

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 Q3524318)