{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T00:33:33Z","timestamp":1773534813198,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540230250","type":"print"},{"value":"9783540301400","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30140-0_54","type":"book-chapter","created":{"date-parts":[[2010,9,19]],"date-time":"2010-09-19T01:31:13Z","timestamp":1284859873000},"page":"604-615","source":"Crossref","is-referenced-by-count":12,"title":["Fast Sparse Matrix Multiplication"],"prefix":"10.1007","author":[{"given":"Raphael","family":"Yuster","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uri","family":"Zwick","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"54_CR1","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. Journal of the ACM\u00a042, 844\u2013856 (1995)","journal-title":"Journal of the ACM"},{"key":"54_CR2","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/BF02523189","volume":"17","author":"N. Alon","year":"1997","unstructured":"Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica\u00a017, 209\u2013223 (1997)","journal-title":"Algorithmica"},{"key":"54_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03338-8","volume-title":"Algebraic complexity theory","author":"P. B\u00fcrgisser","year":"1997","unstructured":"B\u00fcrgisser, P., Clausen, M., Shokrollahi, M.A.: Algebraic complexity theory. Springer, Heidelberg (1997)"},{"key":"54_CR4","doi-asserted-by":"crossref","unstructured":"Chan, T.: Dynamic subgraph connectivity with geometric applications. In: Proc. of 34th STOC, pp. 7\u201313 (2002)","DOI":"10.1145\/509907.509911"},{"key":"54_CR5","doi-asserted-by":"publisher","first-page":"1635","DOI":"10.1137\/S0097539793256223","volume":"26","author":"J. Cheriyan","year":"1997","unstructured":"Cheriyan, J.: Randomized \u00d5(M(|V |)) algorithms for problems in matching theory. SIAM Journal on Computing\u00a026, 1635\u20131655 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"54_CR6","doi-asserted-by":"crossref","unstructured":"Cohn, H., Umans, C.: A group-theoretic approach to fast matrix multiplication. In: Proc. of 44th FOCS, pp. 438\u2013449 (2003)","DOI":"10.1109\/SFCS.2003.1238217"},{"key":"54_CR7","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. Journal of Complexity\u00a013, 42\u201349 (1997)","journal-title":"Journal of Complexity"},{"key":"54_CR8","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\u00a09, 251\u2013280 (1990)","journal-title":"Journal of Symbolic Computation"},{"key":"54_CR9","doi-asserted-by":"crossref","unstructured":"Demetrescu, C., Italiano, G.F.: Fully dynamic transitive closure: Breaking through the O(n 2) barrier. In: Proceedings of FOCS 2000, pp. 381\u2013389 (2000)","DOI":"10.1109\/SFCS.2000.892126"},{"issue":"1","key":"54_CR10","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0020-0190(03)00252-7","volume":"87","author":"F. Eisenbrand","year":"2003","unstructured":"Eisenbrand, F., Grandoni, F.: Detecting directed 4-cycles still faster. Information Processing Letters\u00a087(1), 13\u201315 (2003)","journal-title":"Information Processing Letters"},{"issue":"3","key":"54_CR11","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1145\/355791.355796","volume":"4","author":"F.G. Gustavson","year":"1978","unstructured":"Gustavson, F.G.: Two fast algorithms for sparse matrices: Multiplication and permuted transposition. ACM Transactions on Mathematical Software\u00a04(3), 250\u2013269 (1978)","journal-title":"ACM Transactions on Mathematical Software"},{"key":"54_CR12","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 multiplications and applications. Journal of Complexity\u00a014, 257\u2013299 (1998)","journal-title":"Journal of Complexity"},{"key":"54_CR13","unstructured":"Kratsch, D., Spinrad, J.: Between O(nm) and O(n \u03b1 ). In: Proc. of 14th SODA, pp. 709\u2013716 (2003)"},{"key":"54_CR14","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02579206","volume":"7","author":"K. Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica\u00a07, 105\u2013113 (1987)","journal-title":"Combinatorica"},{"issue":"2","key":"54_CR15","first-page":"415","volume":"26","author":"J. Ne\u0161et\u0159il","year":"1985","unstructured":"Ne\u0161et\u0159il, J., Poljak, S.: On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae\u00a026(2), 415\u2013419 (1985)","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"54_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-13866-8","volume-title":"How to Multiply Matrices Faster","author":"V. Pan","year":"1984","unstructured":"Pan, V.: How to Multiply Matrices Faster. LNCS, vol.\u00a0179. Springer, Heidelberg (1984)"},{"key":"54_CR17","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1016\/0196-6774(89)90005-9","volume":"10","author":"M.O. Rabin","year":"1989","unstructured":"Rabin, M.O., Vazirani, V.V.: Maximum matchings in general graphs through randomization. Journal of Algorithms\u00a010, 557\u2013567 (1989)","journal-title":"Journal of Algorithms"},{"key":"54_CR18","doi-asserted-by":"publisher","first-page":"1356","DOI":"10.1137\/S0097539702402147","volume":"32","author":"R. Raz","year":"2003","unstructured":"Raz, R.: On the complexity of matrix product. SIAM Journal on Computing\u00a032, 1356\u20131369 (2003)","journal-title":"SIAM Journal on Computing"},{"key":"54_CR19","doi-asserted-by":"crossref","unstructured":"Roditty, L., Zwick, U.: Improved dynamic reachability algorithms for directed graphs. In: Proceedings of FOCS 2002, pp. 679\u2013689 (2002)","DOI":"10.1109\/SFCS.2002.1181993"},{"key":"54_CR20","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1995.1078","volume":"51","author":"R. Seidel","year":"1995","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem in unweighted undirected graphs. Journal of Computer and System Sciences\u00a051, 400\u2013403 (1995)","journal-title":"Journal of Computer and System Sciences"},{"key":"54_CR21","doi-asserted-by":"crossref","unstructured":"Shoshan, A., Zwick, U.: All pairs shortest paths in undirected graphs with integer weights. In: Proc. of 40th FOCS, pp. 605\u2013614 (1999)","DOI":"10.1109\/SFFCS.1999.814635"},{"key":"54_CR22","doi-asserted-by":"publisher","first-page":"1185","DOI":"10.1137\/S0097539702405954","volume":"32","author":"A. Shpilka","year":"2003","unstructured":"Shpilka, A.: Lower bounds for matrix product. SIAM Journal on Computing\u00a032, 1185\u20131200 (2003)","journal-title":"SIAM Journal on Computing"},{"key":"54_CR23","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V. Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numerische Mathematik\u00a013, 354\u2013356 (1969)","journal-title":"Numerische Mathematik"},{"key":"54_CR24","unstructured":"Yuster, R., Zwick, U.: Detecting short directed cycles using rectangular matrix multiplication and dynamic programming. In: Proc. of 15th SODA, pp. 247\u2013253 (2004)"},{"key":"54_CR25","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/567112.567114","volume":"49","author":"U. Zwick","year":"2002","unstructured":"Zwick, U.: All-pairs shortest paths using bridging sets and rectangular matrix multiplication. Journal of the ACM\u00a049, 289\u2013317 (2002)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30140-0_54.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T22:38:40Z","timestamp":1740523120000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30140-0_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540230250","9783540301400"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30140-0_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}