{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T03:37:42Z","timestamp":1743046662483,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319130743"},{"type":"electronic","value":"9783319130750"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-13075-0_4","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T16:37:06Z","timestamp":1415983026000},"page":"41-52","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Average-Case Complexity of the Min-Sum Matrix Product Problem"],"prefix":"10.1007","author":[{"given":"Ken","family":"Fong","sequence":"first","affiliation":[]},{"given":"Minming","family":"Li","sequence":"additional","affiliation":[]},{"given":"Hongyu","family":"Liang","sequence":"additional","affiliation":[]},{"given":"Linji","family":"Yang","sequence":"additional","affiliation":[]},{"given":"Hao","family":"Yuan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,8]]},"reference":[{"key":"4_CR1","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Bloniarz, P.A.: A shortest-path algorithm with expected time $${O}(n^2 \\log n\\log ^*n)$$. SIAM Journal on Computing 12(3), 588\u2013600 (1983). http:\/\/link.aip.org\/link\/?SMJ\/12\/588\/1","DOI":"10.1137\/0212039"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Blum, M., Floyd, R.W., Pratt, V., Rivest, R.L., Tarjan, R.E.: Time bounds for selection. Journal of Computer and System Sciences 7(4), 448\u2013461 (1973). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0022000073800339","DOI":"10.1016\/S0022-0000(73)80033-9"},{"issue":"5","key":"4_CR4","doi-asserted-by":"publisher","first-page":"2075","DOI":"10.1137\/08071990X","volume":"39","author":"TM Chan","year":"2010","unstructured":"Chan, T.M.: More algorithms for all-pairs shortest paths in weighted graphs. SIAM Journal on Computing 39(5), 2075\u20132089 (2010)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"4_CR5","doi-asserted-by":"publisher","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. Journal of Symbolic Computation 9(3), 251\u2013280 (1990). http:\/\/www.sciencedirect.com\/science\/article\/pii\/S0747717108800132","journal-title":"Journal of Symbolic Computation"},{"key":"4_CR6","doi-asserted-by":"publisher","DOI":"10.1002\/0471722162","volume-title":"Order Statistics","author":"HA David","year":"2003","unstructured":"David, H.A., Nagaraja, H.N.: Order Statistics. Wiley, Hoboken (2003)"},{"issue":"12","key":"4_CR7","doi-asserted-by":"publisher","first-page":"2549","DOI":"10.1109\/TPAMI.2011.121","volume":"33","author":"PF Felzenszwalb","year":"2011","unstructured":"Felzenszwalb, P.F., McAuley, J.J.: Fast inference with min-sum matrix product. IEEE Transactions on Pattern Analysis and Machine Intelligence 33(12), 2549\u20132554 (2011)","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Fredman, M.L.: On the decision tree complexity of the shortest path problems. In: Proc. 16th FOCS, pp. 98\u201399 (1975)","DOI":"10.1109\/SFCS.1975.22"},{"issue":"1","key":"4_CR9","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"ML Fredman","year":"1976","unstructured":"Fredman, M.L.: New bounds on the complexity of the shortest path problems. SIAM Journal on Computing 5(1), 83\u201389 (1976)","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"4_CR10","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/s00453-007-9063-0","volume":"51","author":"Y Han","year":"2008","unstructured":"Han, Y.: An $${O}(n^3(\\log \\log {n}\/ \\log {n})^{5\/4})$$ time algorithm for all pairs shortest paths. Algorithmica 51(4), 428\u2013434 (2008)","journal-title":"Algorithmica"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Han, Y., Takaoka, T.: An $${O}(n^3 \\log {} \\log {n} \/ \\log ^2 {n})$$ time algorithm for all pairs shortest paths. In: Proc. 13th SWAT (2012)","DOI":"10.1007\/978-3-642-31155-0_12"},{"issue":"6","key":"4_CR12","doi-asserted-by":"publisher","first-page":"1199","DOI":"10.1137\/0222071","volume":"22","author":"D Karger","year":"1993","unstructured":"Karger, D., Koller, D., Phillips, S.: Finding the hidden path: time bounds for all-pairs shortest paths. SIAM Journal on Computing 22(6), 1199\u20131217 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR13","first-page":"525","volume":"9","author":"JJ McAuley","year":"2010","unstructured":"McAuley, J.J., Caetano, T.S.: Exploiting within-clique factorizations in junction-tree algorithms. Journal of Machine Learning Research - Proceedings Track 9, 525\u2013532 (2010)","journal-title":"Journal of Machine Learning Research - Proceedings Track"},{"issue":"5","key":"4_CR14","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1007\/BF01190847","volume":"13","author":"C McGeoch","year":"1995","unstructured":"McGeoch, C.: All-pairs shortest paths and the essential subgraph. Algorithmica 13(5), 426\u2013441 (1995)","journal-title":"Algorithmica"},{"issue":"1\u20132","key":"4_CR15","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/(SICI)1098-2418(199701\/03)10:1\/2<205::AID-RSA11>3.0.CO;2-7","volume":"10","author":"K Mehlhorn","year":"1997","unstructured":"Mehlhorn, K., Priebe, V.: On the all-pairs shortest-path algorithm of Moffat and Takaoka. Random Structures and Algorithms 10(1\u20132), 205\u2013220 (1997)","journal-title":"Random Structures and Algorithms"},{"issue":"6","key":"4_CR16","doi-asserted-by":"publisher","first-page":"1023","DOI":"10.1137\/0216065","volume":"16","author":"A Moffat","year":"1987","unstructured":"Moffat, A., Takaoka, T.: An all pairs shortest path algorithm with expected time $${O}(n^2 \\log {n})$$. SIAM Journal on Computing 16(6), 1023\u20131031 (1987)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Peres, Y., Sotnikov, D., Sudakov, B., Zwick, U.: All-pairs shortest paths in $${O}(n^{2})$$ time with high probability. In: Proc. 51th FOCS, pp. 663\u2013672 (2010)","DOI":"10.1109\/FOCS.2010.69"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Spira, P.M.: A new algorithm for finding all shortest paths in a graph of positive arcs in average time $${O(n^{2} {\\rm {log}}^{2} n)}$$. SIAM Journal on Computing 2(1), 28\u201332 (1973). http:\/\/link.aip.org\/link\/?SMJ\/2\/28\/1","DOI":"10.1137\/0202004"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numerische Mathematik 13(4), 354\u2013356 (1969). http:\/\/dx.doi.org\/10.1007\/BF02165411","DOI":"10.1007\/BF02165411"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Takaoka, T.: Efficient algorithms for the maximum subarray problem by distance matrix multiplication. Electronic Notes in Theoretical Computer Science 61, 191\u2013200 (2002).http:\/\/www.sciencedirect.com\/science\/article\/pii\/S1571066104003135","DOI":"10.1016\/S1571-0661(04)00313-5"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-13075-0_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T19:04:51Z","timestamp":1676660691000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-13075-0_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319130743","9783319130750"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-13075-0_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]},"assertion":[{"value":"8 November 2014","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}