An Efficient Distributed Algoritm for the Weighted Shortest-path Updating Problem


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 7, No. 6, pp. 1778-1784, Jun. 2000
10.3745/KIPSTE.2000.7.6.1778,   PDF Download:

Abstract

We consider the weighted shortest path updating problem, that is, the problem to reconstruct the weighted shortest paths in response to topology change of the network. This appear proposes a distributed algorithms that reconstructs the weighted shortest paths after several processors and links are added and deleted. its message complexity and ideal-time complexity are O(p$^2$ 수식 이미지+q+n``) and O(p$^2$ 수식 이미지+q+n``) respectively, where n`` is the number of processors in the network after the topology change, q is the number of added links, and p is the total number of processors in he biconnected components (of the network before the topology change) 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, K. O. Lee, K. C. Kang, "An Efficient Distributed Algoritm for the Weighted Shortest-path Updating Problem," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 7, no. 6, pp. 1778-1784, 2000. DOI: 10.3745/KIPSTE.2000.7.6.1778.

[ACM Style]
Jeong Ho Park, Kyung Oh Lee, and Kyu Chul Kang. 2000. An Efficient Distributed Algoritm for the Weighted Shortest-path Updating Problem. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 7, 6, (2000), 1778-1784. DOI: 10.3745/KIPSTE.2000.7.6.1778.