{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:44:27Z","timestamp":1787499867226,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540424949","type":"print"},{"value":"9783540446798","type":"electronic"}],"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-44679-6_30","type":"book-chapter","created":{"date-parts":[[2010,2,9]],"date-time":"2010-02-09T12:00:37Z","timestamp":1265716837000},"page":"268-277","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["A Space Saving Trick for Directed Dynamic Transitive Closure and Shortest Path Algorithms"],"prefix":"10.1007","author":[{"given":"Valerie","family":"King","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mikkel","family":"Thorup","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2001,7,31]]},"reference":[{"key":"30_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon, Z. Galil, O. Margalit, and M. Naor Witnesses for boolean matrix multiplication and for shortest paths. In Proceedings of the 33rd IEEE Annual Symposium on Foundations of Computer Science, pages 417\u2013426, 1992.","DOI":"10.1109\/SFCS.1992.267748"},{"key":"30_CR2","unstructured":"G. Brown and V. King Space-efficent methods for maintaining shortest paths and transitive closure: Theory and practice, August 2000. Presentation at Workshop on Efficient Algorithms at Oberwolfach."},{"key":"30_CR3","unstructured":"C. Demetrescu Fully Dynamic Algorithms for Path Problems on Directed Graphs. PhD thesis, Dip. Informatica e Sistemistica Universita\u2019 di Roma \u201cLa Sapienza\u201d, 2000."},{"key":"30_CR4","doi-asserted-by":"crossref","unstructured":"C. Demetrescu and G. Italiano Fully dynamic transitive closure: Breaking through the o(n 2) barrier. In Proc. 41st IEEE Symp. on Foundations of Computer Science, pages 381\u2013389, 2000.","DOI":"10.1109\/SFCS.2000.892126"},{"issue":"1","key":"30_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/322234.322235","volume":"28","author":"S. Even","year":"1981","unstructured":"S. Even and Y. Shiloach An on-line edge-deletion problem. J. ACM, 28(1):1\u20134, 1981.","journal-title":"J. ACM"},{"key":"30_CR6","doi-asserted-by":"crossref","unstructured":"Bernard Fortz and Mikkel Thorup Internet traffic engineering by optimizing OSPF weights. In Proc. 19th IEEE INFOCOM-The Conference on Computer Communications, pages 519\u2013528, 2000.","DOI":"10.1109\/INFCOM.2000.832225"},{"key":"30_CR7","doi-asserted-by":"crossref","unstructured":"D. Frigioni, M. Ioffreda, U. Nanni, and G. Pasqualone Experimental analysis of dynamic algorithms for the single-source shortest path problem. ACM Jounal of Experimental Algorithmics, 3, article 5, 1998.","DOI":"10.1145\/297096.297147"},{"issue":"5","key":"30_CR8","first-page":"1250","volume":"11","author":"M.E. Furman","year":"1970","unstructured":"M.E. Furman Application of a method of rapid multiplication of matrices to the problem of finding the transitive closure of a graph. Soviet Math. Dokl., 11(5):1250, 1970.","journal-title":"Soviet Math. Dokl"},{"key":"30_CR9","doi-asserted-by":"crossref","unstructured":"V. King Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In Proc. 40th IEEE Symp. on Foundations of Computer Science, pages 81\u201389, 1999.","DOI":"10.1109\/SFFCS.1999.814580"},{"issue":"2","key":"30_CR10","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/0020-0190(71)90006-8","volume":"1","author":"I. Munro","year":"1971","unstructured":"I. Munro Efficient determination of the transitive closure of a directed graph. Information Processing Letters, 1(2):56\u201358, 1971.","journal-title":"Information Processing Letters"},{"issue":"2","key":"30_CR11","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1006\/jagm.1996.0046","volume":"21","author":"G. Ramalingam","year":"1996","unstructured":"G. Ramalingam and T.W. Reps An incremental algorithm for a generalization of the shortest-path problem. Journal of Algorithms, 21(2):267\u2013305, 1996.","journal-title":"Journal of Algorithms"},{"key":"30_CR12","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R.E. Tarjan","year":"1972","unstructured":"R.E. Tarjan Deep-first search and linear graph algorithms. SIAM J. Computing, 1:146\u2013160, 1972.","journal-title":"SIAM J. Computing"},{"key":"30_CR13","doi-asserted-by":"crossref","unstructured":"U. Zwick All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms. In Proceedings of the 39rd IEEE Annual Symposium on Foundations of Computer Science, pages 310\u2013319, 1998.","DOI":"10.1109\/SFCS.1998.743464"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44679-6_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,17]],"date-time":"2025-02-17T22:34:51Z","timestamp":1739831691000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44679-6_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424949","9783540446798"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-44679-6_30","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"31 July 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}