{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T06:26:55Z","timestamp":1743316015745,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540425120"},{"type":"electronic","value":"9783540446910"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44691-5_19","type":"book-chapter","created":{"date-parts":[[2007,6,2]],"date-time":"2007-06-02T22:32:07Z","timestamp":1180823527000},"page":"218-229","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Maintaining Shortest Paths in Digraphs with Arbitrary Arc Weights: An Experimental Study"],"prefix":"10.1007","author":[{"given":"Camil","family":"Demetrescu","sequence":"first","affiliation":[]},{"given":"Daniele","family":"Frigioni","sequence":"additional","affiliation":[]},{"given":"Alberto","family":"Marchetti-Spaccamela","sequence":"additional","affiliation":[]},{"given":"Umberto","family":"Nanni","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,24]]},"reference":[{"key":"19_CR1","unstructured":"R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs, NJ, 1993."},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"D. Alberts, G. Cattaneo, and G. F. Italiano. An empirical study of dynamic graph algorithms. ACM Journal on Experimental Algorithmics, 2:Article 5, 1997.","DOI":"10.1145\/264216.264223"},{"key":"19_CR3","unstructured":"G. Amato, G. Cattaneo, and G. F. Italiano. Experimental analysis of dynamic minimum spanning tree algorithms. In ACM-SIAM Symp. on Discrete Algorithms, pp. 1\u201310, 1997."},{"key":"19_CR4","unstructured":"B. V. Cherkassky and A. V. Goldberg. Negative-cycle detection algorithms. In European Symp. on Algorithms. Lect. Notes in Comp. Sc. 1136, pp. 349\u2013363, 1996."},{"key":"19_CR5","first-page":"129","volume":"73","author":"B. V. Cherkassky","year":"1996","unstructured":"B. V. Cherkassky, A. V. Goldberg, and T. Radzik. Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming, 73:129\u2013174, 1996.","journal-title":"Mathematical Programming"},{"key":"19_CR6","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"J. Edmonds, R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19:248\u2013264, 1972.","journal-title":"Journal of the ACM"},{"key":"19_CR7","unstructured":"P. G. Franciosa, D. Frigioni, and R. Giaccio. Semi-dynamic shortest paths and breadth-first search on digraphs. In Symp. on Theoretical Aspects of Computer Science. Lect. Notes in Comp. Sc. 1200, pp. 33\u201346, 1997."},{"key":"19_CR8","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/297096.297147","volume":"3","author":"D. Frigioni","year":"1998","unstructured":"D. Frigioni, M. Ioffreda, U. Nanni, G. Pasqualone. Experimental Analysis of Dynamic Algorithms for the Single Source Shortest Path Problem. ACM Journal on Experimental Algorithmics, 3:Article 5 (1998).","journal-title":"ACM Journal on Experimental Algorithmics"},{"issue":"2","key":"19_CR9","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1006\/jagm.1999.1048","volume":"34","author":"D. Frigioni","year":"2000","unstructured":"D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni. Fully dynamic algorithms for maintaining shortest paths trees. Journal of Algorithms, 34(2):351\u2013381, 2000.","journal-title":"Journal of Algorithms"},{"key":"19_CR10","unstructured":"D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni. Fully dynamic shortest paths and negative cycles detection on digraphs with arbitrary arc weights. In European Symp. on Algorithms. Lect. Notes in Comp. Sc. 1461, pp. 320\u2013331, 1998."},{"key":"19_CR11","unstructured":"D. Frigioni, T. Miller, U. Nanni, G. Pasqualone, G. Shaefer, C. Zaroliagis. An experimental study of dynamic algorithms for directed graphs. In European Symp. on Algorithms. Lect. Notes in Comp. Sc. 1461, pp. 368\u2013380, 1998."},{"key":"19_CR12","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg. Selecting problems for algorithm evaluation. In Workshop on Algorithm Engineering. Lect. Notes in Comp. Sc. 1668, pp. 1\u201311, 1999.","DOI":"10.1007\/3-540-48318-7_1"},{"key":"19_CR13","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0893-9659(93)90022-F","volume":"6","author":"A. V. Goldberg","year":"1993","unstructured":"A. V. Goldberg, and T. Radzik. A heuristic improvement of the Bellman-Ford algorithm. Applied Math. Letters, 6:3\u20136, 1993.","journal-title":"Applied Math. Letters"},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1145\/204865.204889","volume":"38","author":"K. Mehlhorn","year":"1995","unstructured":"K. Mehlhorn and S. Naher. LEDA, a platform for combinatorial and geometric computing. Communications of the ACM, 38:96\u2013102, 1995.","journal-title":"Communications of the ACM"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"G. Ramalingam. Bounded incremental computation. Lect. Notes in Comp. Sc. 1089, 1996.","DOI":"10.1007\/BFb0028290"},{"key":"19_CR16","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0304-3975(95)00079-8","volume":"158","author":"G. Ramalingam","year":"1996","unstructured":"G. Ramalingam and T. Reps. On the computational complexity of dynamic graph problems. Theoretical Computer Science, 158:233\u2013277, 1996.","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44691-5_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,29]],"date-time":"2020-04-29T13:04:43Z","timestamp":1588165483000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44691-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540425120","9783540446910"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-44691-5_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"24 August 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}