A Distributed Algorithm to Update Span~ning Tree and Strongly-Connected Components


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 6, No. 2, pp. 299-306, Feb. 1999
10.3745/KIPSTE.1999.6.2.299,   PDF Download:

Abstract

Considers the problem to update the spanning tree and strongly-connected components in response to topology change of the network. This paper proposes a 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 O(n'log n'+(n'+ s+t)) and O(n'log n') respectively, where n' is the number of processors in the network after the topology change, s is the number of added links, and t is the total number of links in the strongly connected component (of the network before the topology change) including the deleted 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, P. Y. Young, C. S. Hee, "A Distributed Algorithm to Update Span~ning Tree and Strongly-Connected Components," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 6, no. 2, pp. 299-306, 1999. DOI: 10.3745/KIPSTE.1999.6.2.299.

[ACM Style]
Park Jung Ho, Park Yoon Young, and Choi Sung Hee. 1999. A Distributed Algorithm to Update Span~ning Tree and Strongly-Connected Components. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 6, 2, (1999), 299-306. DOI: 10.3745/KIPSTE.1999.6.2.299.