{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T22:43:57Z","timestamp":1791326637134,"version":"4.3.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2006,10]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1198513.1198519","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T15:20:08Z","timestamp":1175786408000},"page":"578-601","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":57,"title":["Experimental analysis of dynamic all pairs shortest path algorithms"],"prefix":"10.1145","volume":"2","author":[{"given":"Camil","family":"Demetrescu","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Rome, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \u201cTor Vergata\u201d, Rome, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/264216.264223"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'97)","author":"Amato G.","unstructured":"Amato , G. , Cattaneo , G. , and Italiano , G . 1997. Experimental analysis of dynamic minimum spanning tree algorithms . In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'97) . ACM, New York, 314--323.]] Amato, G., Cattaneo, G., and Italiano, G. 1997. Experimental analysis of dynamic minimum spanning tree algorithms. In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'97). ACM, New York, 314--323.]]"},{"key":"e_1_2_1_3_1","volume-title":"Tech. Rep. TD--5RJ8B, AT&T Labs--Research.]]","author":"Buriol L.","year":"2003","unstructured":"Buriol , L. , Resende , M. , and Thorup , M . 2003 . Speeding up dynamic shortest path algorithms. Tech. Rep. TD--5RJ8B, AT&T Labs--Research.]] Buriol, L., Resende, M., and Thorup, M. 2003. Speeding up dynamic shortest path algorithms. Tech. Rep. TD--5RJ8B, AT&T Labs--Research.]]"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 4th International Workshop on Algorithm Engineering and Experiments (ALENEX'02)","author":"Cattaneo G.","unstructured":"Cattaneo , G. , Faruolo , P. , Ferraro-Petrillo , U. , and Italiano , G . 2002. Maintaining dynamic minimum spanning trees: An experimental study . In Proceedings of the 4th International Workshop on Algorithm Engineering and Experiments (ALENEX'02) .]] Cattaneo, G., Faruolo, P., Ferraro-Petrillo, U., and Italiano, G. 2002. Maintaining dynamic minimum spanning trees: An experimental study. In Proceedings of the 4th International Workshop on Algorithm Engineering and Experiments (ALENEX'02).]]"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3226663.3227073"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 4th Workshop on Algorithm Engineering (WAE'00)","author":"Demetrescu C.","unstructured":"Demetrescu , C. , Frigioni , D. , Marchetti-Spaccamela , A. , and Nanni , U . 2000. Maintaining shortest paths in digraphs with arbitrary arc weights: An experimental study . In Proceedings of the 4th Workshop on Algorithm Engineering (WAE'00) (Saarbr\u00fccken, Germany, Sept. 5--8).]] Demetrescu, C., Frigioni, D., Marchetti-Spaccamela, A., and Nanni, U. 2000. Maintaining shortest paths in digraphs with arbitrary arc weights: An experimental study. In Proceedings of the 4th Workshop on Algorithm Engineering (WAE'00) (Saarbr\u00fccken, Germany, Sept. 5--8).]]"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780567"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039492"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.05.005"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322235"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 19th IEEE INFOCOM---The Conference on Computer Communications. IEEE Computer Society Press","author":"Fortz B.","unstructured":"Fortz , B. , and Thorup , M . 2000. Internet traffic engineering by optimizing OSPF weights . In Proceedings of the 19th IEEE INFOCOM---The Conference on Computer Communications. IEEE Computer Society Press , Los Alamitos, CA, 519--528.]] Fortz, B., and Thorup, M. 2000. Internet traffic engineering by optimizing OSPF weights. In Proceedings of the 19th IEEE INFOCOM---The Conference on Computer Communications. IEEE Computer Society Press, Los Alamitos, CA, 519--528.]]"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/297096.297147"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the European Symposium on Algorithms (ESA'98)","volume":"1461","author":"Frigioni D.","unstructured":"Frigioni , D. , Miller , T. , Nanni , U. , Pasqualone , G. , Shaefer , G. , and Zaroliagis , C . 1998b. An experimental study of dynamic algorithms for directed graphs . In Proceedings of the European Symposium on Algorithms (ESA'98) . Lecture Notes in Computer Science , vol. 1461 . Springer-Verlag, New York, 320--331.]] Frigioni, D., Miller, T., Nanni, U., Pasqualone, G., Shaefer, G., and Zaroliagis, C. 1998b. An experimental study of dynamic algorithms for directed graphs. In Proceedings of the European Symposium on Algorithms (ESA'98). Lecture Notes in Computer Science, vol. 1461. Springer-Verlag, New York, 320--331.]]"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45678-3_43"},{"key":"e_1_2_1_17_1","unstructured":"Greene D. and Knuth D. 1982. Mathematics for the analysis of algorithms. Birkh\u00e4user.]]   Greene D. and Knuth D. 1982. Mathematics for the analysis of algorithms. Birkh\u00e4user.]]"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 2nd International Workshop on Algorithm Engineering and Experiments (ALENEX'00)","author":"Iyer R.","unstructured":"Iyer , R. , Karger , D. R. , Rahul , H. S. , and Thorup , M . 2000. An experimental study of poly-logarithmic fully-dynamic connectivity algorithms . In Proceedings of the 2nd International Workshop on Algorithm Engineering and Experiments (ALENEX'00) , B. Moret and A. Goldberg, Eds.]] Iyer, R., Karger, D. R., Rahul, H. S., and Thorup, M. 2000. An experimental study of poly-logarithmic fully-dynamic connectivity algorithms. In Proceedings of the 2nd International Workshop on Algorithm Engineering and Experiments (ALENEX'00), B. Moret and A. Goldberg, Eds.]]"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222071"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796487"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 7th Annual International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science","volume":"2108","author":"King V.","unstructured":"King , V. , and Thorup , M . 2001. A space saving trick for directed dynamic transitive closure and shortest path algorithms . In Proceedings of the 7th Annual International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science , vol. 2108 . Springer-Verlag, New York, 268--277.]] King, V., and Thorup, M. 2001. A space saving trick for directed dynamic transitive closure and shortest path algorithms. In Proceedings of the 7th Annual International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science, vol. 2108. Springer-Verlag, New York, 268--277.]]"},{"key":"e_1_2_1_22_1","first-page":"96","article-title":"A network evaluation procedure","volume":"205","author":"Loubal P.","year":"1967","unstructured":"Loubal , P. 1967 . A network evaluation procedure . Highway Res. Rec. 205 , 96 -- 109 .]] Loubal, P. 1967. A network evaluation procedure. Highway Res. Rec. 205, 96--109.]]","journal-title":"Highway Res. Rec."},{"key":"e_1_2_1_23_1","volume-title":"The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph","author":"Murchland J.","unstructured":"Murchland , J. 1967. The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph . Tech. Rep., LBS-TNT-26, London Business School, Transport Network Theory Unit, London, UK. ]] Murchland, J. 1967. The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph. Tech. Rep., LBS-TNT-26, London Business School, Transport Network Theory Unit, London, UK.]]"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.893870"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/90.974525"},{"key":"e_1_2_1_26_1","series-title":"Lecture Notes in Computer Science","volume-title":"Bounded incremental computation","author":"Ramalingam G.","unstructured":"Ramalingam , G. 1996. Bounded incremental computation . Lecture Notes in Computer Science , vol. 1089 . Springer-Verlag , New York .]] Ramalingam, G. 1996. Bounded incremental computation. Lecture Notes in Computer Science, vol. 1089. Springer-Verlag, New York.]]"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0046"},{"key":"e_1_2_1_28_1","unstructured":"Seward J. and Nethercote N. 2003. Valgrind an open-source memory debugger for x86-gnu\/linux. URL: http:\/\/developer.kde.org\/~sewardj\/.]]  Seward J. and Nethercote N. 2003. Valgrind an open-source memory debugger for x86-gnu\/linux. URL: http:\/\/developer.kde.org\/~sewardj\/.]]"},{"key":"e_1_2_1_29_1","series-title":"Lecture Notes in Computer Science","volume-title":"Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles","author":"Thorup M.","unstructured":"Thorup , M. 2004. Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles . In SWAT, T. Hagerup and J. Katajainen, Eds. Lecture Notes in Computer Science , vol. 3111 . Springer-Verlag , New York , 384--396.]] Thorup, M. 2004. Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In SWAT, T. Hagerup and J. Katajainen, Eds. Lecture Notes in Computer Science, vol. 3111. Springer-Verlag, New York, 384--396.]]"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.32.1.65"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1198513.1198519","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T15:33:05Z","timestamp":1672241585000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1198513.1198519"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,10]]}},"alternative-id":["10.1145\/1198513.1198519"],"URL":"https:\/\/doi.org\/10.1145\/1198513.1198519","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,10]]},"assertion":[{"value":"2006-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}