A Fast Distributed Approximation Algorithm for Minimum Spanning Trees

DOI10.1007/11864219_25zbMATH Open1155.68562OpenAlexW2136425424MaRDI QIDQ3524318FDOQ3524318

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

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

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)

Cited In (20)

• Computing and Combinatorics
• Title not available (Why is that?)
• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
• A faster distributed protocol for constructing a minimum spanning tree
• 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
• Distributed algorithms for low stretch spanning trees
• Title not available (Why is that?)
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• A linear-time optimal-message distributed algorithm for minimum spanning trees
• Faster Fully-Dynamic Minimum Spanning Forest
• Distributed approximation of minimum routing cost trees
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• 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
• Silent MST Approximation for Tiny Memory
• Energy-efficient cooperative data aggregation for wireless sensor networks
• Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model

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)