A Sub-Linear Time Distributed Algorithm for Minimum-Weight Spanning Trees (Extended Abstract)

This paper considers the question of identifying the parameters governing the behavior of fundamental global network problems. Many papers on distributed network algorithms consider the task of optimizing the running time successful when an O(n) bound is achieved on an n-vertex network. We propose that a more sensitive parameter is the network's diameter Diam. This is demonstrated in the paper by providing a distributed minimum-weight spanning tree algorithm whose time complexity is sub-linear in n, but linear in Diam (specifically, O(Diam+n/sup 0. 614/)). Our result is achieved through the application of graph decomposition and edge elimination techniques that may be of independent interest. >

Authors

• Juan A. Garay 0001
• Shay Kutten
• David Peleg

Keywords

• Distributed algorithms
• Cities and towns
• USA Councils
• Tree graphs
• Nominations and elections
• Mathematics
• Career development
• Global Positioning System
• Distributed Algorithm
• Spanning Tree
• Running Time
• Time Complexity
• Network Diameter
• Interesting Question
• Stage 2
• Tree Structure
• Edge Weights
• Cycle Length
• Original Algorithm
• Subtree
• Minimum Weight
• Complex Communication
• Multiple Edges
• Final Tree
• Forest Fragments
• Outgoing Edges
• Pipelining
• N Log N
• Minimum Edge
• Adjacent Fragments
• Core Edge
• Short Elimination
• Adjacent Nodes
• Original Network
• Unit Time