{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,6]],"date-time":"2025-04-06T18:43:10Z","timestamp":1743964990792,"version":"3.33.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2008,1,25]],"date-time":"2008-01-25T00:00:00Z","timestamp":1201219200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,2]]},"DOI":"10.1007\/s00453-008-9166-2","type":"journal-article","created":{"date-parts":[[2008,1,24]],"date-time":"2008-01-24T18:28:20Z","timestamp":1201199300000},"page":"180-197","source":"Crossref","is-referenced-by-count":15,"title":["Fast Dynamic Transitive Closure with Lookahead"],"prefix":"10.1007","volume":"56","author":[{"given":"Piotr","family":"Sankowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Mucha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,1,25]]},"reference":[{"key":"9166_CR1","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1090\/S0025-5718-1974-0331751-8","volume":"28","author":"J. Bunch","year":"1974","unstructured":"Bunch, J., Hopcroft, J.: Triangular factorization and inversion by fast matrix multiplication. Math. Comput. 28, 231\u2013236 (1974)","journal-title":"Math. Comput."},{"issue":"1","key":"9166_CR2","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1006\/jcom.1997.0438","volume":"13","author":"D. Coppersmith","year":"1997","unstructured":"Coppersmith, D.: Rectangular matrix multiplication revisited. J. Complex. 13(1), 42\u201349 (1997)","journal-title":"J. Complex."},{"issue":"3","key":"9166_CR3","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"Coppersmith, D., Winograd, S.: Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9(3), 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"9166_CR4","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Italiano, G.F.: Fully dynamic transitive closure: Breaking through the O(n 2) barrier. In: Proceedings of the 40th IEEE Symposium on Foundations of Computer Science, pp. 381\u2013389 (2000)","DOI":"10.1109\/SFCS.2000.892126"},{"issue":"1","key":"9166_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/322234.322235","volume":"28","author":"S. Even","year":"1981","unstructured":"Even, S., Shiloach, Y.: An on-line edge-deletion problem. J. ACM 28(1), 1\u20134 (1981)","journal-title":"J. ACM"},{"key":"9166_CR6","doi-asserted-by":"crossref","unstructured":"Henzinger, M.R., King, V.: Fully dynamic biconnectivity and transitive closure. In: Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, pp. 664\u2013672 (1995)","DOI":"10.1109\/SFCS.1995.492668"},{"issue":"2","key":"9166_CR7","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1006\/jcom.1998.0476","volume":"14","author":"X. Huang","year":"1998","unstructured":"Huang, X., Pan, V.Y.: Fast rectangular matrix multiplication and applications. J. Complex. 14(2), 257\u2013299 (1998)","journal-title":"J. Complex."},{"issue":"4","key":"9166_CR8","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1007\/PL00009220","volume":"21","author":"S. Khanna","year":"1998","unstructured":"Khanna, S., Motwani, R., Wilson, R.H.: On certificates and lookahead in dynamic graph problems. Algorithmica 21(4), 377\u2013394 (1998)","journal-title":"Algorithmica"},{"key":"9166_CR9","doi-asserted-by":"crossref","unstructured":"King, V.: Fully dynamic algorithms for maintaining all-pairs shortest paths and transitive closure in digraphs. In: Proceedings of the 40th IEEE Symposium on Foundations of Computer Science, pp. 81\u201391 (1999)","DOI":"10.1109\/SFFCS.1999.814580"},{"key":"9166_CR10","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1145\/301250.301380","volume-title":"Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing","author":"V. King","year":"1999","unstructured":"King, V., Sagert, G.: A fully dynamic algorithm for maintaining the transitive closure. In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pp. 492\u2013498. ACM, New York (1999)"},{"key":"9166_CR11","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1137\/0716027","volume":"16","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Rose, D.J., Tarjan, R.E.: Generalized nested dissection. SIAM J. Numer. Anal. 16, 346\u2013358 (1979)","journal-title":"SIAM J. Numer. Anal."},{"key":"9166_CR12","first-page":"404","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"L. Roditty","year":"2003","unstructured":"Roditty, L.: A faster and simpler fully dynamic transitive closure. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 404\u2013412. Society for Industrial and Applied Mathematics, Philadelphia (2003)"},{"key":"9166_CR13","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: Improved dynamic reachability algorithms for directed graphs. In: Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, p. 679 (2002)","DOI":"10.1109\/SFCS.2002.1181993"},{"key":"9166_CR14","volume-title":"Proceeding of the 36th Annual ACM Symposium on Theory of Computing","author":"L. Roditty","year":"2004","unstructured":"Roditty, L., Zwick, U.: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. In: Proceeding of the 36th Annual ACM Symposium on Theory of Computing. ACM, New York (2004)"},{"key":"9166_CR15","doi-asserted-by":"crossref","unstructured":"Sankowski, P.: Dynamic transitive closure via dynamic matrix inverse. In: 45th Annual IEEE Symposium on Foundations of Computer Science (2004)","DOI":"10.1109\/FOCS.2004.25"},{"key":"9166_CR16","first-page":"118","volume-title":"SODA \u201907: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"P. Sankowski","year":"2007","unstructured":"Sankowski, P.: Faster dynamic matchings and vertex connectivity. In: SODA \u201907: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 118\u2013126. Society for Industrial and Applied Mathematics, Philadelphia (2007)"},{"key":"9166_CR17","first-page":"701","volume":"10","author":"J.T. Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. Algorithms 10, 701\u2013717 (1980)","journal-title":"J. Algorithms"},{"key":"9166_CR18","first-page":"372","volume-title":"Proceedings of the First Annual European Symposium on Algorithms","author":"S. Subramanian","year":"1993","unstructured":"Subramanian, S.: A fully dynamic data structure for reachability in planar digraphs. In: Proceedings of the First Annual European Symposium on Algorithms, pp. 372\u2013383. Springer, New York (1993)"},{"key":"9166_CR19","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1145\/298514.298576","volume-title":"Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems","author":"M. Yannakakis","year":"1990","unstructured":"Yannakakis, M.: Graph-theoretic methods in database theory. In: Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 230\u2013242. ACM, New York (1990)"},{"key":"9166_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Proceedings of EUROSAM 79","author":"R.E. Zippel","year":"1979","unstructured":"Zippel, R.E.: Probabilistic algorithms for sparse polynomials. In: Proceedings of EUROSAM 79. Lecture Notes in Computer Science, vol. 72, pp. 216\u2013226. Springer, New York (1979)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9166-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-008-9166-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-008-9166-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,26]],"date-time":"2025-01-26T07:24:29Z","timestamp":1737876269000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-008-9166-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1,25]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["9166"],"URL":"https:\/\/doi.org\/10.1007\/s00453-008-9166-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2008,1,25]]}}}