ISSN : 1796-203X
Volume : 2    Issue : 9    Date : November 2007

Partially Dynamic Algorithms for Distributed Shortest Paths and their Experimental Evaluation
Serafino Cicerone, Gianlorenzo D’Angelo, Gabriele Di Stefano, Daniele Frigioni, and Alberto
Page(s): 16-26
Full Text:
PDF (425 KB)

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