Distributed Algorithm for Updating Minimum - Weight Spanning Tree Problem


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 1, No. 2, pp. 184-193, Jul. 1994
10.3745/KIPSTE.1994.1.2.184,   PDF Download:

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 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. Moreover the last part of this paper touches on the algorithm which deals with deletion and addition of processors as well as links.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
P. J. Ho and M. J. Young, "Distributed Algorithm for Updating Minimum - Weight Spanning Tree Problem," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 1, no. 2, pp. 184-193, 1994. DOI: 10.3745/KIPSTE.1994.1.2.184.

[ACM Style]
Park Jung Ho and Min Joon Young. 1994. Distributed Algorithm for Updating Minimum - Weight Spanning Tree Problem. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 1, 2, (1994), 184-193. DOI: 10.3745/KIPSTE.1994.1.2.184.