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, Camil; Giuseppe F., Italiano. - In: ACM TRANSACTIONS ON ALGORITHMS. - ISSN 1549-6325. - 2:4(2006), pp. 578-601. (Intervento presentato al convegno 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04) tenutosi a New Orleans, Louisiana nel January 2004) [10.1145/1198513.1198519].
Experimental Analysis of Dynamic All Pairs Shortest Path Algorithms
DEMETRESCU, Camil;
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.| File | Dimensione | Formato | |
|---|---|---|---|
|
VE_2006_11573-129782.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
916.28 kB
Formato
Adobe PDF
|
916.28 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
