{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T17:10:01Z","timestamp":1737479401350,"version":"3.33.0"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,10,13]],"date-time":"2007-10-13T00:00:00Z","timestamp":1192233600000},"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":[[2008,8]]},"DOI":"10.1007\/s00453-007-9051-4","type":"journal-article","created":{"date-parts":[[2007,10,12]],"date-time":"2007-10-12T17:57:26Z","timestamp":1192211846000},"page":"387-427","source":"Crossref","is-referenced-by-count":6,"title":["Mantaining Dynamic Matrices for Fully Dynamic Transitive Closure"],"prefix":"10.1007","volume":"51","author":[{"given":"Camil","family":"Demetrescu","sequence":"first","affiliation":[]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,10,13]]},"reference":[{"key":"9051_CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading (1974)"},{"key":"9051_CR2","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, 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"key":"9051_CR3","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)"},{"key":"9051_CR4","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Italiano, G.F.: Fully dynamic transitive closure: breaking through the O(n 2) barrier. In: Proc. of the 41st IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201900), pp. 381\u2013389 (2000)","DOI":"10.1109\/SFCS.2000.892126"},{"issue":"2","key":"9051_CR5","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1145\/1059513.1059514","volume":"52","author":"C. Demetrescu","year":"2005","unstructured":"Demetrescu, C., Italiano, G.F.: Trade-offs for fully dynamic reachability on dags: breaking through the O(n 2) barrier. J. Assoc. Comput. Mach. (J. ACM) 52(2), 147\u2013156 (2005)","journal-title":"J. Assoc. Comput. Mach. (J. ACM)"},{"key":"9051_CR6","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\u20134 (1981)","journal-title":"J. ACM"},{"key":"9051_CR7","doi-asserted-by":"crossref","unstructured":"Fischer, M.J., Meyer, A.R.: Boolean matrix multiplication and transitive closure. In: Conference Record 1971 Twelfth Annual Symposium on Switching and Automata Theory, East Lansing, Michigan, 13\u201315 October 1971, pp. 129\u2013131. IEEE","DOI":"10.1109\/SWAT.1971.4"},{"key":"9051_CR8","unstructured":"Furman, M.E.: Application of a method of fast multiplication of matrices in the problem of finding the transitive closure of a graph. Sov. Math. Dokl. 11(5) (1970). English translation"},{"key":"9051_CR9","doi-asserted-by":"crossref","unstructured":"Henzinger, M., King, V.: Fully dynamic biconnectivity and transitive closure. In: Proc. 36th IEEE Symposium on Foundations of Computer Science (FOCS\u201995), pp. 664\u2013672 (1995)","DOI":"10.1109\/SFCS.1995.492668"},{"key":"9051_CR10","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0020-0190(83)90033-9","volume":"16","author":"T. Ibaraki","year":"1983","unstructured":"Ibaraki, T., Katoh, N.: On-line computation of transitive closure for graphs. Inf. Process. Lett. 16, 95\u201397 (1983)","journal-title":"Inf. Process. Lett."},{"issue":"2\u20133","key":"9051_CR11","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0304-3975(86)90098-8","volume":"48","author":"G.F. Italiano","year":"1986","unstructured":"Italiano, G.F.: Amortized efficiency of a path retrieval data structure. Theor. Comput. Sci. 48(2\u20133), 273\u2013281 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"9051_CR12","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/0020-0190(88)90136-6","volume":"28","author":"G.F. Italiano","year":"1988","unstructured":"Italiano, G.F.: Finding paths and deleting edges in directed acyclic graphs. Inf. Process. Lett. 28, 5\u201311 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9051_CR13","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":"9051_CR14","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\u201999), pp. 81\u201399 (1999)","DOI":"10.1109\/SFFCS.1999.814580"},{"issue":"1","key":"9051_CR15","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1006\/jcss.2002.1883","volume":"65","author":"V. King","year":"2002","unstructured":"King, V., Sagert, G.: A fully dynamic algorithm for maintaining the transitive closure. J. Comput. Syst. Sci. 65(1), 150\u2013167 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"9051_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1007\/3-540-19422-3_9","volume-title":"Proc. Workshop on Graph-Theoretic Concepts in Computer Science","author":"J.A. La Poutr\u00e9","year":"1988","unstructured":"La Poutr\u00e9, J.A., van Leeuwen, J.: Maintenance of transitive closure and transitive reduction of graphs. In: Proc. Workshop on Graph-Theoretic Concepts in Computer Science. Lecture Notes in Computer Science, vol. 314, pp. 106\u2013120. Springer, Berlin (1988)"},{"key":"9051_CR17","doi-asserted-by":"crossref","unstructured":"Mucha, M., Sankowski, P.: Maximum matchings via Gaussian elimination. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201904), pp. 248\u2013255 (2004)","DOI":"10.1109\/FOCS.2004.40"},{"issue":"2","key":"9051_CR18","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/0020-0190(71)90006-8","volume":"1","author":"I. Munro","year":"1971","unstructured":"Munro, I.: Efficient determination of the transitive closure of a directed graph. Inf. Process. Lett. 1(2), 56\u201358 (1971)","journal-title":"Inf. Process. Lett."},{"key":"9051_CR19","unstructured":"Roditty, L.: A faster and simpler fully dynamic transitive closure. In: Proceedings of the 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, MD, USA, pp. 404\u2013412 (2003)"},{"key":"9051_CR20","doi-asserted-by":"crossref","unstructured":"Sankowski, P.: Dynamic transitive closure via dynamic matrix inverse. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201904), Rome, Italy, pp. 509\u2013517 (2004)","DOI":"10.1109\/FOCS.2004.25"},{"key":"9051_CR21","doi-asserted-by":"crossref","unstructured":"Sankowski, P.: Subquadratic algorithm for dynamic shortest distances. In: Proceedings of the 11th Annual International Conference on Computing and Combinatorics (COCOON\u201905), pp. 461\u2013470 (2005)","DOI":"10.1007\/11533719_47"},{"key":"9051_CR22","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BF01209711","volume":"30","author":"D.M. Yellin","year":"1993","unstructured":"Yellin, D.M.: Speeding up dynamic transitive closure for bounded degree graphs. Acta Inf. 30, 369\u2013384 (1993)","journal-title":"Acta Inf."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9051-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9051-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9051-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T16:56:31Z","timestamp":1737478591000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9051-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,13]]},"references-count":22,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["9051"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9051-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2007,10,13]]}}}