An Efficient Distributed Algorithm to Solve Breadth - First Spannnig Tree Updating Problem


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 7, No. 5, pp. 1370-1376, May. 2000
10.3745/KIPSTE.2000.7.5.1370,   PDF Download:

Abstract

Consider the problem to update Breadth-First Spanning Tree in response to topology change of the network. This paper proposes an efficient distributed algorithm that solves such a problem after several processors and links are added and deleted. Its message complexity and its ideal-time complexity are Ο(p√q q a n') respectively, where n' is the number of processors in the network after the topology change, a is the number of added links, p is the total number of links in the biconnected component (of the network before the topology change) including the deleted links or added links, and q is the total number of processors in the biconnected component including the deleted links or added 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]
J. H. Park, Y. Y. Park, S. H. Hwang, "An Efficient Distributed Algorithm to Solve Breadth - First Spannnig Tree Updating Problem," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 7, no. 5, pp. 1370-1376, 2000. DOI: 10.3745/KIPSTE.2000.7.5.1370.

[ACM Style]
Jung Ho Park, Yoon Young Park, and Suk Hyung Hwang. 2000. An Efficient Distributed Algorithm to Solve Breadth - First Spannnig Tree Updating Problem. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 7, 5, (2000), 1370-1376. DOI: 10.3745/KIPSTE.2000.7.5.1370.