Distributed MST for constant diameter graphs

DOI10.1007/s00446-005-0127-6zbMath1266.68219MaRDI QIDQ5919895

Zvi Lotker, Boaz Patt-Shamir, David Peleg

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

zbMATH Keywords

distributed algorithm; minimum-weight spanning tree

Mathematics Subject Classification ID

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

Distributed Graph Algorithms and their Complexity: An Introduction, Tight bounds for parallel randomized load balancing, Fast and compact self-stabilizing verification, computation, and fault detection of an MST, Local MST computation with short advice, On the complexity of distributed stable matching with small messages, Sub-logarithmic distributed algorithms for metric facility location, Lessons from the congested clique applied to MapReduce, A fast distributed approximation algorithm for minimum spanning trees, Low-congestion shortcut and graph parameters, 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