{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T17:25:44Z","timestamp":1725470744215},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540388753"},{"type":"electronic","value":"9783540388760"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11841036_65","type":"book-chapter","created":{"date-parts":[[2006,9,11]],"date-time":"2006-09-11T13:20:54Z","timestamp":1157980854000},"page":"732-743","source":"Crossref","is-referenced-by-count":2,"title":["Does Path Cleaning Help in Dynamic All-Pairs Shortest Paths?"],"prefix":"10.1007","author":[{"given":"C.","family":"Demetrescu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P.","family":"Faruolo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G. F.","family":"Italiano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Thorup","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"65_CR1","unstructured":"Buriol, L., Resende, M., Thorup, M.: Speeding up dynamic shortest path algorithms. Technical report, AT&T Labs Research Report TD5RJ8B (2003)"},{"key":"65_CR2","unstructured":"Demetrescu, C., Emiliozzi, S., Finocchi, I., Ribichini, A.: The Leonardo Library, http:\/\/www.leonardo-vm.org"},{"key":"65_CR3","unstructured":"Demetrescu, C., Emiliozzi, S., Italiano, G.F.: Experimental analysis of dynamic all pairs shortest path algorithms. In: Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 362\u2013371 (2004)"},{"key":"65_CR4","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithm Engineering","author":"C. Demetrescu","year":"2001","unstructured":"Demetrescu, C., Frigioni, D., Marchetti-Spaccamela, A., Nanni, U.: Maintaining shortest paths in digraphs with arbitrary arc weights: An experimental study. In: N\u00e4her, S., Wagner, D. (eds.) WAE 2000. LNCS, vol.\u00a01982. Springer, Heidelberg (2001)"},{"issue":"6","key":"65_CR5","doi-asserted-by":"crossref","first-page":"968","DOI":"10.1145\/1039488.1039492","volume":"51","author":"C. Demetrescu","year":"2004","unstructured":"Demetrescu, C., Italiano, G.F.: A new approach to dynamic all pairs shortest paths. J. ACM\u00a051(6), 968\u2013992 (2004) (preliminary version in STOC 2003)","journal-title":"J. ACM"},{"key":"65_CR6","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik\u00a01, 269\u2013271 (1959)","journal-title":"Numerische Mathematik"},{"key":"65_CR7","doi-asserted-by":"crossref","unstructured":"Fortz, B., Thorup, M.: Internet traffic engineering by optimizing OSPF weights. In: Proc. 19th IEEE INFOCOM, pp. 519\u2013528 (2000)","DOI":"10.1109\/INFCOM.2000.832225"},{"key":"65_CR8","doi-asserted-by":"crossref","unstructured":"Frigioni, D., Ioffreda, M., Nanni, U., Pasqualone, G.: Analysis of dynamic algorithms for the single source shortest path problem. ACM Journal on Experimental Algorithmics\u00a03 (1998)","DOI":"10.1145\/297096.297147"},{"key":"65_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1007\/3-540-68530-8_27","volume-title":"Algorithms - ESA \u201998","author":"D. Frigioni","year":"1998","unstructured":"Frigioni, D., Miller, T., Nanni, U., Pasqualone, G., Shaefer, G., Zaroliagis, C.D.: An experimental study of dynamic algorithms for directed graphs. In: Bilardi, G., Pietracaprina, A., Italiano, G.F., Pucci, G. (eds.) ESA 1998. LNCS, vol.\u00a01461, pp. 320\u2013331. Springer, Heidelberg (1998)"},{"key":"65_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45678-3_43","volume-title":"Algorithms and Computation","author":"A.V. Goldberg","year":"2001","unstructured":"Goldberg, A.V.: Shortest path algorithms: Engineering aspects. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001. LNCS, vol.\u00a02223. Springer, Heidelberg (2001)"},{"issue":"2","key":"65_CR11","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1137\/S0097539797327209","volume":"31","author":"M.R. Henzinger","year":"2001","unstructured":"Henzinger, M.R., King, V.: Maintaining minimum spanning forests in dynamic graphs. SIAM J. Computing\u00a031(2), 364\u2013374 (2001)","journal-title":"SIAM J. Computing"},{"key":"65_CR12","doi-asserted-by":"crossref","unstructured":"King, V.: Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proc. 40th IEEE Symposium on Foundations of Computer Science (FOCS 1999), pp. 81\u201399 (1999)","DOI":"10.1109\/SFFCS.1999.814580"},{"key":"65_CR13","first-page":"96","volume":"205","author":"P. Loubal","year":"1967","unstructured":"Loubal, P.: A network evaluation procedure. Highway Research Record\u00a0205, 96\u2013109 (1967)","journal-title":"Highway Research Record"},{"key":"65_CR14","doi-asserted-by":"publisher","first-page":"706","DOI":"10.1109\/90.974525","volume":"9","author":"P. Narvaez","year":"2001","unstructured":"Narvaez, P., Siu, K.Y., Tzeng, H.Y.: New dynamic SPT algorithm based on a ball-and-string model. IEEE\/ACM Transactions on Networking\u00a09, 706\u2013718 (2001)","journal-title":"IEEE\/ACM Transactions on Networking"},{"key":"65_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028290","volume-title":"Bounded Incremental Computation","author":"G. Ramalingam","year":"1996","unstructured":"Ramalingam, G.: Bounded Incremental Computation. LNCS, vol.\u00a01089. Springer, Heidelberg (1996)"},{"key":"65_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1007\/978-3-540-27810-8_33","volume-title":"Algorithm Theory - SWAT 2004","author":"M. Thorup","year":"2004","unstructured":"Thorup, M.: Fully-dynamic all-pairs shortest paths: Faster and allowing negative cycles. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol.\u00a03111, pp. 384\u2013396. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11841036_65.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:40:37Z","timestamp":1605642037000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11841036_65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540388753","9783540388760"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/11841036_65","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}