Distrbuted Processing and An Algorithm Solving the Biconnected-components Reconstruction Problem


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 5, No. 10, pp. 2512-2520, Oct. 1998
10.3745/KIPSTE.1998.5.10.2512,   PDF Download:

Abstract

This paper considers the Biconnected-components Reconstruction Problem(BRP), that is, the problem to reconstruct the biconnected-components in response to topology change of the network. This paper proposes a distributed algorithm that solves the BRP after several processors and links are added and deleted. Its message complexity and its ideal-time complexity are O(n' a b) and O(n') respectively, where n' is the number of processors in the network after the topology change, a is the number of added links, and b is the total number of links in the biconnected components (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]
L. C. Suk, P. J. Ho, K. Y. Seol, "Distrbuted Processing and An Algorithm Solving the Biconnected-components Reconstruction Problem," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 5, no. 10, pp. 2512-2520, 1998. DOI: 10.3745/KIPSTE.1998.5.10.2512.

[ACM Style]
Lee Chang Suk, Park Jung Ho, and Koo Yeon Seol. 1998. Distrbuted Processing and An Algorithm Solving the Biconnected-components Reconstruction Problem. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 5, 10, (1998), 2512-2520. DOI: 10.3745/KIPSTE.1998.5.10.2512.