Efficient distributed algorithm to solve updating minimum spanning tree problem
Jung‐Ho Park, Kenichi Hagihara, Nobuki Tokura, Toshimitsu Masuzawa · Systems and Computers in Japan · 1992
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.