JCP 2007 Vol.2(9): 16-26 ISSN: 1796-203X
doi: 10.4304/jcp.2.9.16-26
doi: 10.4304/jcp.2.9.16-26
Partially Dynamic Algorithms for Distributed Shortest Paths and their Experimental Evaluation
Serafino Cicerone, Gianlorenzo D’Angelo, Gabriele Di Stefano, Daniele Frigioni, Alberto Petricola
1Dipartimento di Ingegneria Elettrica e dell’Informazione
Universit`a dell’Aquila, I-67040 Monteluco di Roio, L’Aquila, Italy
Abstract—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.
Index Terms—Distributed networks, dynamic algorithms, shortest paths, routing, experimental evaluation, network simulation environment
Abstract—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.
Index Terms—Distributed networks, dynamic algorithms, shortest paths, routing, experimental evaluation, network simulation environment
Cite: Serafino Cicerone, Gianlorenzo D’Angelo, Gabriele Di Stefano, Daniele Frigioni, Alberto Petricola, "Partially Dynamic Algorithms for Distributed Shortest Paths and their Experimental Evaluation," Journal of Computers vol. 2, no.9, pp. 16-26 , 2007.
General Information
ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Abbreviated Title: J.Comput.
Frequency: Bimonthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO, ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat,etc
E-mail: jcp@iap.org
-
Nov 14, 2019 News!
Vol 14, No 11 has been published with online version [Click]
-
Mar 20, 2020 News!
Vol 15, No 2 has been published with online version [Click]
-
Dec 16, 2019 News!
Vol 14, No 12 has been published with online version [Click]
-
Sep 16, 2019 News!
Vol 14, No 9 has been published with online version [Click]
-
Aug 16, 2019 News!
Vol 14, No 8 has been published with online version [Click]
- Read more>>