ALCOMFT-TR-03-9

Camil Demetrescu, Stefano Emiliozzi and Giuseppe F. Italiano
Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms
Rome. Work packages 2, 4 and 5. July 2003.

Abstract: We present the results of an extensive computational study on dynamic algorithms for all pairs shortest path problems. We describe our implementations of the recent dynamic algorithms of King [FOCS-99] and of Demetrescu and Italiano [STOC-03], and compare them to the dynamic algorithm of Ramalingam and Reps [JALGO-21-96] and to static algorithms on random, real-world and hard instances. Our experimental data suggest that some of the dynamic algorithms and their algorithmic techniques can be really of practical value in many situations.

Postscript file: ALCOMFT-TR-03-9.ps.gz (257 kb).