Abstract
This paper considers the Updating Minimum-weight Spanning Tree Problem (UMP), that is, the problem to update the Minimum-weight Spanning Tree (MST) in response to topology change of the network. This paper proposes the algorithm which reconstructs the MST after several links are deleted and added. Its message complexity and its ideal-time complexity are O(m+n log (t+f)) and O(n+n log(t+f)) respectively, where n is the number of processors in the network, t (resp. f) is the number of added links (resp. the number of deleted links of the old MST), and m=t+n if f=0, m=e (i.e. the number of links in the network after the topology change) otherwise. The last part of this paper touches on the algorithm which deals with deletion and addition of processors as well as links.
This work was supported in part by the Scientific Research Grant-in-Aid from Ministry of Education, Science and Culture of Japan, the Mazda Foundation's Research Grant and the Inamori Foundation's Research Grant.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
B. Awerbuch: "Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election and related problems", Proceedings 19th Annual ACM Symposium on Theory of Computing, pp.230–240(1987).
I.Cimet and S.P.Kumar: "A Resilient Distributed Algorithms for Minimum Weight Spanning Trees", Proceedings of the 1987 International Conference on Parallel Processing., pp.196–203(1987).
R. Gallager, P. Humblet and P. Spira: "A Distributed Algorithm for Minimum Weight Spanning Trees", ACM TOPLAS, 5, 1, pp.66–77(1983).
J.Park, T.Masuzawa, K.Hagihara and N.Tokura: "Distributed Algorithms for Reconstructing Minimum Spanning Tree — The Case of Link Deletions —", Tech. Rep. IECEJ, COMP-89-25(in Japanese) (1989).
Y.H.Tsin: "An Asynchronous Distributed MST Updating Algorithm for Handling Vertex Insertions in Networks", Proc. of the International Conference on Parallel Processing and Applications, pp.221–226(1987).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Park, J., Masuzawa, T., Hagihara, K., Tokura, N. (1991). Distributed algorithms for reconstructing MST after topology change. In: van Leeuwen, J., Santoro, N. (eds) Distributed Algorithms. WDAG 1990. Lecture Notes in Computer Science, vol 486. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54099-7_9
Download citation
DOI: https://doi.org/10.1007/3-540-54099-7_9
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54099-1
Online ISBN: 978-3-540-47405-0
eBook Packages: Springer Book Archive