Distributed MST for constant diameter graphs
From MaRDI portal
Publication:5919895
DOI10.1007/s00446-005-0127-6zbMath1266.68219MaRDI QIDQ5919895
David Peleg, Boaz Patt-Shamir, Zvi Lotker
Publication date: 13 June 2013
Published in: Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00446-005-0127-6
05C05: Trees
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68W20: Randomized algorithms
68W15: Distributed algorithms
Related Items
Local MST computation with short advice, On the complexity of distributed stable matching with small messages, A fast distributed approximation algorithm for minimum spanning trees, Distributed Disaster Disclosure
Cites Work
- Unnamed Item
- Unnamed Item
- A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
- Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
- How to share memory in a distributed system
- New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- Locality in Distributed Graph Algorithms
- Fast Distributed Construction of Smallk-Dominating Sets and Applications
- Sharing memory robustly in message-passing systems
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
- Distributed Computing: A Locality-Sensitive Approach
- Optimal distributed algorithm for minimum spanning trees revisited
- Parallelism in random access machines
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
