{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:10:58Z","timestamp":1725567058707},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540280613"},{"type":"electronic","value":"9783540318064"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11533719_47","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T13:34:13Z","timestamp":1127828053000},"page":"461-470","source":"Crossref","is-referenced-by-count":17,"title":["Subquadratic Algorithm for Dynamic Shortest Distances"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Sankowski","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"47_CR1","doi-asserted-by":"publisher","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. Comp.\u00a028, 231\u2013236 (1974)","journal-title":"Math. Comp."},{"issue":"1","key":"47_CR2","doi-asserted-by":"publisher","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.\u00a013(1), 42\u201349 (1997)","journal-title":"J. Complex."},{"key":"47_CR3","first-page":"1","volume-title":"Proceedings of the nineteenth annual ACM symposium on Theory of Computing","author":"D. Coppersmith","year":"1987","unstructured":"Coppersmith, D., Winograd, S.: Matrix Multiplication via Arithmetic Progressions. In: Proceedings of the nineteenth annual ACM symposium on Theory of Computing, pp. 1\u20136. ACM Press, New York (1987)"},{"key":"47_CR4","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Italiano, G.F.: Fully Dynamic All Pairs Shortest Paths with Real Edge Weights. In: Proceedings of 42th annual IEEE Symposium on Foundations of Computer Science, pp. 260\u2013267 (2001)","DOI":"10.1109\/SFCS.2001.959900"},{"key":"47_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"633","DOI":"10.1007\/3-540-45465-9_54","volume-title":"Automata, Languages and Programming","author":"C. Demetrescu","year":"2002","unstructured":"Demetrescu, C., Italiano, G.F.: Improved Bounds and New Trade-Offs for Dynamic All Pairs Shortest Paths. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 633\u2013643. Springer, Heidelberg (2002)"},{"key":"47_CR6","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1145\/780542.780567","volume-title":"Proceedings of the thirty-fifth annual ACM Symposium on Theory of Computing","author":"C. Demetrescu","year":"2003","unstructured":"Demetrescu, C., Italiano, G.F.: A new Approach to Dynamic all Pairs Shortest Paths. In: Proceedings of the thirty-fifth annual ACM Symposium on Theory of Computing, pp. 159\u2013166. ACM Press, New York (2003)"},{"key":"47_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/3-540-49116-3_34","volume-title":"STACS 99","author":"G.S. Frandsen","year":"1999","unstructured":"Frandsen, G.S., Hansen, J.P., Miltersen, P.B.: Lower Bounds for Dynamic Algebraic Problems. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol.\u00a01563, pp. 362\u2013372. Springer, Heidelberg (1999)"},{"key":"47_CR8","volume-title":"Mathematics for the Analysis of Algorithms","author":"D.H. Greene","year":"1982","unstructured":"Greene, D.H., Knuth, D.E.: Mathematics for the Analysis of Algorithms. Birkh\u00e4user, Basel (1982)"},{"key":"47_CR9","doi-asserted-by":"crossref","unstructured":"Henzinger, M.R., King, V.: Fully Dynamic Biconnectivity and Transitive Closure. In: Proceedings 36th annual IEEE Symposiumon Foundations of Computer Science, pp. 664\u2013672 (1995)","DOI":"10.1109\/SFCS.1995.492668"},{"issue":"2","key":"47_CR10","doi-asserted-by":"publisher","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. Journal of complexity\u00a014(2), 257\u2013299 (1998)","journal-title":"Journal of complexity"},{"key":"47_CR11","doi-asserted-by":"crossref","unstructured":"King, V.: Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs. In: Proceedings of 40th annual IEEE Symposium on Foundations of Computer Science, pp. 81\u201391 (1999)","DOI":"10.1109\/SFFCS.1999.814580"},{"issue":"2","key":"47_CR12","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1145\/322063.322068","volume":"25","author":"H.T. Kung","year":"1978","unstructured":"Kung, H.T., Traub, J.F.: All Algebraic Functions Can Be Computed Fast. J. ACM\u00a025(2), 245\u2013260 (1978)","journal-title":"J. ACM"},{"issue":"2","key":"47_CR13","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1006\/jagm.1995.0807","volume":"22","author":"J.H. Reif","year":"1997","unstructured":"Reif, J.H., Tate, S.R.: On Dynamic Algorithms for Algebraic Problems. J. Algorithms\u00a022(2), 347\u2013371 (1997)","journal-title":"J. Algorithms"},{"key":"47_CR14","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, pp. 509\u2013517 (2004)","DOI":"10.1109\/FOCS.2004.25"},{"key":"47_CR15","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/BF02242355","volume":"7","author":"A. Schonhage","year":"1971","unstructured":"Schonhage, A., Strassen, V.: Schnelle Multiplikation grosser Zahlen. Computing\u00a07, 281\u2013292 (1971)","journal-title":"Computing"},{"key":"47_CR16","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\u00a010, 701\u2013717 (1980)","journal-title":"J. Algorithms"},{"key":"47_CR17","first-page":"182","volume":"264","author":"V. Strassen","year":"1973","unstructured":"Strassen, V.: Vermeidung von Divisionen. J. reine u. angew. Math.\u00a0264, 182\u2013202 (1973)","journal-title":"J. reine u. angew. Math."},{"key":"47_CR18","doi-asserted-by":"crossref","unstructured":"Ullman, J., Yannakakis, M.: High-probability Parallel Transitive Closure Algorithms. In: Proceedings of the 1990 ACM Symposium on Parallel Algorithms and Architectures, July 1990, pp. 200\u2013209 (1990)","DOI":"10.1145\/97444.97686"},{"key":"47_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation","author":"R.E. Zippel","year":"1979","unstructured":"Zippel, R.E.: Probabilistic Algorithms for Sparse Polynomials. In: Ng, K.W. (ed.) EUROSAM 1979 and ISSAC 1979. LNCS, vol.\u00a072, pp. 216\u2013226. Springer, Heidelberg (1979)"},{"key":"47_CR20","doi-asserted-by":"crossref","unstructured":"Zwick, U.: All Pairs Shortest Paths in Weighted Directed Graphs Exact and Almost Exact Algorithms. In: Proceedings of the 39th annual IEEE Symposium on Foundations of Computer Science, pp. 310\u2013319 (1998)","DOI":"10.1109\/SFCS.1998.743464"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11533719_47","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,18]],"date-time":"2021-07-18T03:09:59Z","timestamp":1626577799000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11533719_47"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540280613","9783540318064"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11533719_47","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}