DISTRIBUTED ALGORITHMS SOLVING THE UPDATING PROBLEMS

다국어 초록 (Multilingual Abstract)

In this paper, we consider the updating problems to reconstruct the biconnected-components and to reconstruct the weighted shortest path in response to the topology change of the network. We propose two distributed algorithms. The first algorithm solves the updating problem that reconstructs the biconnected-components after the several processors and links are added and deleted. Its bit complexity is O((n′ + a + d) log n′), its message complexity is O(n′ + a + d), the ideal time complexity is O(n′), and the space complexity is O(e log n + e′ log n′). The second algorithm solves the updating problem that reconstructs the weighted shortest path. Its message complexity and ideal-time complexity are O(u_(2) + a + n′) respectively.

목차 (Table of Contents)

• 1. Introduction
• 2. Preliminaries
• 2.1 Distributed system model
• 2.2 Biconnected-component Updating Problem(BUP)
• 2.3 The weighted-Shortest Updating Problem(SUP)
• 2.4 Measures of efficiency
• 3. Algorithm solving the BUP
• 3.1 Properties of the biconnected components
• 3.2 Description of the algorithm for the BUP
• 3.3 Complexities
• 4. Algorithm solving the SUP
• 4.1 The idea of our algorithm for the SUP
• 4.2 Outline of our algorithm for the SUP
• 4.3 Complexities
• 5. Conclusions
• REFERENCES