{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,28]],"date-time":"2025-07-28T21:11:48Z","timestamp":1753737108655},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540291183"},{"type":"electronic","value":"9783540319511"}],"license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11561071_68","type":"book-chapter","created":{"date-parts":[[2005,10,6]],"date-time":"2005-10-06T08:46:24Z","timestamp":1128588384000},"page":"770-778","source":"Crossref","is-referenced-by-count":18,"title":["Shortest Paths in Matrix Multiplication Time"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Sankowski","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"68_CR1","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"R. Bellman","year":"1958","unstructured":"Bellman, R.: On a Routing Problem. Quarterly of Applied Mathematics\u00a016(1), 87\u201390 (1958)","journal-title":"Quarterly of Applied Mathematics"},{"key":"68_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/28395.28396","volume-title":"Proceedings of the nineteenth annual ACM conference 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 conference on Theory of computing, pp. 1\u20136. ACM Press, New York (1987)"},{"key":"68_CR3","volume-title":"Introduction to Algorithms","author":"T.H. Cormen","year":"1990","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. MIT Press, Cambridge (1990)"},{"issue":"2","key":"68_CR4","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/0022-0000(85)90039-X","volume":"31","author":"H.N. Gabow","year":"1985","unstructured":"Gabow, H.N.: Scaling Algorithms for Network Problems. J. Comput. Syst. Sci.\u00a031(2), 148\u2013168 (1985)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"68_CR5","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1137\/0218069","volume":"18","author":"H.N. Gabow","year":"1989","unstructured":"Gabow, H.N., Tarjan, R.E.: Faster Scaling Algorithms for Network Problems. SIAM J. Comput.\u00a018(5), 1013\u20131036 (1989)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"68_CR6","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1137\/S0097539792231179","volume":"24","author":"A.V. Goldberg","year":"1995","unstructured":"Goldberg, A.V.: Scaling Algorithms for the Shortest Paths Problem. SIAM J. Comput.\u00a024(3), 494\u2013504 (1995)","journal-title":"SIAM J. Comput."},{"key":"68_CR7","unstructured":"Ford Jr. L.R.: Network Flow Theory. Paper P-923, The RAND Corperation, Santa Moncia, California (August 1956)"},{"key":"68_CR8","first-page":"285","volume-title":"Proceedings of the International Symposium on the Theory of Switching","author":"E.F. Moore","year":"1959","unstructured":"Moore, E.F.: The Shortest Path Through a Maze. In: Proceedings of the International Symposium on the Theory of Switching, pp. 285\u2013292. Harvard University Press, Cambridge (1959)"},{"key":"68_CR9","unstructured":"Sankowski, P.: Dynamic Transitive Closure via Dynamic Matrix Inverse. In: Proceedings of the 45th annual IEEE Symposium on Foundations of Computer Science, pp. 248\u2013255 (2004)"},{"key":"68_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/11533719_47","volume-title":"Computing and Combinatorics","author":"P. Sankowski","year":"2005","unstructured":"Sankowski, P.: Subquadratic Algorithm for Dynamic Shortest Distances. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 461\u2013470. Springer, Heidelberg (2005)"},{"key":"68_CR11","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J. Schwartz","year":"1980","unstructured":"Schwartz, J.: Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM\u00a027, 701\u2013717 (1980)","journal-title":"Journal of the ACM"},{"key":"68_CR12","first-page":"199","volume-title":"Proceedings of the Symposium on Information Networks","author":"A. Shimbel","year":"1955","unstructured":"Shimbel, A.: Structure in Communication Nets. In: Proceedings of the Symposium on Information Networks, pp. 199\u2013203. Polytechnic Press of the Polytechnic Institute of Brooklyn, Brooklyn (1955)"},{"issue":"3-4","key":"68_CR13","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1016\/S0747-7171(03)00097-X","volume":"36","author":"A. Storjohann","year":"2003","unstructured":"Storjohann, A.: High-order lifting and integrality certification. J. Symb. Comput.\u00a036(3-4), 613\u2013648 (2003)","journal-title":"J. Symb. Comput."},{"key":"68_CR14","unstructured":"Yuster, R., Zwick, U.: Answering distance queries in directed graphs using fast matrix multiplication. In: The 46th Annual Symposium on Foundations of Computer Science, FOCS 2005 (2005)"},{"key":"68_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation","author":"R. Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, K.W. (ed.) EUROSAM 1979 and ISSAC 1979. LNCS, vol.\u00a072, pp. 216\u2013226. Springer, Heidelberg (1979)"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2005"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11561071_68","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T13:15:39Z","timestamp":1578489339000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11561071_68"}},"subtitle":["[Extended Abstract]"],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540291183","9783540319511"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/11561071_68","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}