Distributive Graph Algorithms-Global Solutions from Local Data

This paper deals with distributed graph algorithms. Processors reside in the vertices of a graph G and communicate only with their neighbors. The system is synchronous and reliable, there is no limit on message lengths and local computation is instantaneous. The results: A maximal independent set in an n-cycle cannot be found faster than Ω(log* n) and this is optimal by [CV]. The d-regular tree of radius r cannot be colored with fewer than √d colors in time 2r / 3. If Δ is the largest degree in G which has order n, then in time O(log*n) it can be colored with O(Δ2) colors.

Authors

• Nati Linial

Keywords

• Distributed computing
• Tree graphs
• Power system modeling
• Labeling
• Concurrent computing
• Mathematics
• Computer science
• Color
• Distributed processing
• Computational modeling
• Maximal Set
• Maximum Independent Set
• Lower Bound
• Time Complexity
• Finite Set
• Distributed Algorithm
• Largest Degree
• Graph Of Order
• Distributed Fashion
• Prime Power
• Existence Of Family