Efficient distributed algorithm to solve updating minimum spanning tree problem
✍ Scribed by Jungho Park; Ken'Ichi Hagihara; Nobuki Tokura; Toshimitsu Masuzawa
- Publisher
- John Wiley and Sons
- Year
- 1992
- Tongue
- English
- Weight
- 983 KB
- Volume
- 23
- Category
- Article
- ISSN
- 0882-1666
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
This paper proposes a distributed algorithm for reconstructing a minimum‐weight spanning tree T′ of a network N′ when link addition and deletion occur in a network N with a minimum‐weight spanning tree T. In this algorithm each processor uses information whose adjacent links belong to T in order to construct T′ efficiently. The communication complexity and ideal time complexity of the algorithm are O(n log__(f + t) + m)__ and O(n log__(f + t) + n)__, respectively, where n and e are the number of processors and that of links in N′, t is the number of added links, and f represents that of deleted links belonging to T. Here, m = n + t when f = 0 and m = e otherwise.
This paper also presents a distributed algorithm for reconstructing a minimum‐weight spanning tree T+ when links and processors are added and deleted. The communication complexity and ideal time complexity of the algorithm are O(n log__(g + h) + r__ and O(n log__(g + h)__ + n), respectively, where g is the total number of added links (including links incident to added processors) and h represents the number of deleted links belonging to T (including links incident to deleted processors). Thus, r = n + g when h = 0 and r = e when h > 0.