최단 경로 갱신문제를 해결하는 분산알고리듬 = An Efficient Distributed Algoritm for the Weighted Shortest-path Updating Problem

다국어 초록 (Multilingual 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.