Partially Dynamic Algorithms for Distributed Shortest Paths and their Experimental Evaluation

作     者：Cicerone, Serafino D'Angelo, Gianlorenzo Di Stefano, Gabriele Frigioni, Daniele Petricola, Alberto 

作者机构：Univ Aquila Dipartimento Ingn Elettr & Informaz I-67040 Laquila Italy 

出 版 物：《JOURNAL OF COMPUTERS》 (计算机杂志)

年 卷 期：2007年第2卷第9期

页      面：16-26页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Future and Emerging Technologies Unit of EC [FP6-021235-2] 

主　　题：Distributed networks dynamic algorithms shortest paths routing experimental evaluation network simulation environment 

摘      要：In this paper, we study the dynamic version of the distributed all-pairs shortest paths problem. Most of the solutions given in the literature for this problem, either (i) work under the assumption that before dealing with an edge operation, the algorithm for the previous operation has to be terminated, that is, they are not able to update shortest paths concurrently, or (ii) concurrently update shortest paths, but their convergence can be very slow (possibly infinite). In this paper we propose a partially dynamic algorithm that overcomes most of these limitations. In particular, it is able to concurrently update shortest paths and in many cases its convergence is quite fast. These properties are highlighted by an experimental study whose aim is to show the effectiveness of the proposed algorithms also in the practical case.