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 [1999] and of Demetrescu and Italiano [2006], and compare them to the dynamic algorithm of Ramalingam and Reps 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.

Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms / Demetrescu, C; Italiano, Giuseppe Francesco. - In: ACM TRANSACTIONS ON ALGORITHMS. - ISSN 1549-6325. - 2:4(2006), pp. 578-601. [10.1145/1198513.1198519]

Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms

ITALIANO G
2006

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 [1999] and of Demetrescu and Italiano [2006], and compare them to the dynamic algorithm of Ramalingam and Reps 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.
2006
Design and Analysis of Algorithms; Shortest Path Algorithms; Algorithm Engineering
Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms / Demetrescu, C; Italiano, Giuseppe Francesco. - In: ACM TRANSACTIONS ON ALGORITHMS. - ISSN 1549-6325. - 2:4(2006), pp. 578-601. [10.1145/1198513.1198519]
File in questo prodotto:
File Dimensione Formato  
p578-demetrescu.pdf

Solo gestori archivio

Tipologia: Versione dell'editore
Licenza: DRM (Digital rights management) non definiti
Dimensione 916.28 kB
Formato Adobe PDF
916.28 kB Adobe PDF   Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/199807
Citazioni
  • Scopus 59
  • ???jsp.display-item.citation.isi??? 44
social impact