{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T12:07:09Z","timestamp":1698408429999},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2010,9,14]],"date-time":"2010-09-14T00:00:00Z","timestamp":1284422400000},"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":[[2011,9]]},"DOI":"10.1007\/s00453-010-9441-x","type":"journal-article","created":{"date-parts":[[2010,9,13]],"date-time":"2010-09-13T20:29:19Z","timestamp":1284409759000},"page":"36-50","source":"Crossref","is-referenced-by-count":8,"title":["A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication"],"prefix":"10.1007","volume":"61","author":[{"given":"Andrzej","family":"Lingas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,9,14]]},"reference":[{"issue":"2","key":"9441_CR1","doi-asserted-by":"crossref","first-page":"781","DOI":"10.4007\/annals.2004.160.781","volume":"160","author":"M. Agrawal","year":"2004","unstructured":"Agrawal, M., Kayal, N., Saxena, N.: PRIMES is in P. Ann. Math. 160(2), 781\u2013793 (2004)","journal-title":"Ann. Math."},{"key":"9441_CR2","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1007\/BF01940874","volume":"16","author":"N. Alon","year":"1996","unstructured":"Alon, N., Naor, M.: Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. Algorithmica 16, 434\u2013449 (1996)","journal-title":"Algorithmica"},{"key":"9441_CR3","doi-asserted-by":"crossref","unstructured":"Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. In: Proc. STOC 1996, pp.\u00a020\u201329 (1996)","DOI":"10.1145\/237814.237823"},{"key":"9441_CR4","doi-asserted-by":"crossref","unstructured":"Amossen, R.R., Pagh, R.: Faster join-projects and sparse matrix multiplication. In: Proc. ACM International Conference on Database Theory (ICDT 2009), St. Petersburg, pp. 121\u2013126, March 2009","DOI":"10.1145\/1514894.1514909"},{"key":"9441_CR5","first-page":"1209","volume":"11","author":"V.L. Arlazow","year":"1970","unstructured":"Arlazow, V.L., Dinic, E.A., Kronrod, M.A., Faradzev, I.A.: On economical construction of the transitive closure of an oriented graph. Sov. Math. Dokl. 11, 1209\u20131210 (1970)","journal-title":"Sov. Math. Dokl."},{"key":"9441_CR6","unstructured":"Bash, J., Khanna, S., Motwani, R.: On diameter verification and Boolean matrix multiplication. Technical Report, Stanford University CS department (1995)"},{"key":"9441_CR7","doi-asserted-by":"crossref","first-page":"630","DOI":"10.1006\/jcss.1999.1690","volume":"60","author":"A.Z. Broder","year":"2000","unstructured":"Broder, A.Z., Charikar, M., Frieze, A.M., Mitzenmacher, M.: Min-wise independent permutations. J.\u00a0Comput. Syst. Sci. 60, 630\u2013659 (2000)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9441_CR8","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0885-064X(89)90015-0","volume":"5","author":"B. Chor","year":"1989","unstructured":"Chor, B., Goldreich, O.: On the power of two-point sampling. J. Complex. 5, 96\u2013106 (1989)","journal-title":"J. Complex."},{"key":"9441_CR9","unstructured":"Cohen, E.: Estimating the size of the transitive closure in linear time. In: Proc. FOCS 1994, pp.\u00a0190\u2013200 (1994)"},{"key":"9441_CR10","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1023\/A:1009716300509","volume":"2","author":"E. Cohen","year":"1999","unstructured":"Cohen, E.: Structure prediction and computation of sparse matrix products. J. Comb. Optim. 2, 307\u2013332 (1999)","journal-title":"J. Comb. Optim."},{"key":"9441_CR11","first-page":"42","volume":"13","author":"D. Coppersmith","year":"1997","unstructured":"Coppersmith, D.: Rectangular matrix multiplication revisited. J. Symb. Comput. 13, 42\u201349 (1997)","journal-title":"J. Symb. Comput."},{"key":"9441_CR12","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."},{"issue":"1\u20132","key":"9441_CR13","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/j.tcs.2007.02.053","volume":"380","author":"A. Czumaj","year":"2007","unstructured":"Czumaj, A., Kowaluk, M., Lingas, A.: Faster algorithms for finding lowest common ancestors in directed acyclic graphs. Theor. Comput. Sci. 380(1\u20132), 37\u201346 (2007). The special ICALP 2005 issue","journal-title":"Theor. Comput. Sci."},{"key":"9441_CR14","unstructured":"Galil, Z., Margalit, O.: Witnesses for Boolean matrix multiplication and shortest paths. J. Complex. 417\u2013426 (1993)"},{"key":"9441_CR15","series-title":"The IMA Volumes in Mathematics and Its Applications","volume-title":"Graph Theory and Sparse Matrix Computation","year":"1993","unstructured":"George, A., Gilbert, J., Liu, J.W.H. (eds.): Graph Theory and Sparse Matrix Computation. The IMA Volumes in Mathematics and Its Applications, vol.\u00a056. Springer, Berlin (1993)"},{"key":"9441_CR16","volume-title":"Matrix Computations","year":"1989","unstructured":"Golub, G., Van Loan, C. (eds.): Matrix Computations. Johns Hopkins University Press, Baltimore (1989)"},{"key":"9441_CR17","doi-asserted-by":"crossref","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. J. Complex. 14, 257\u2013299 (1998)","journal-title":"J. Complex."},{"key":"9441_CR18","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1214\/aop\/1176996762","volume":"2","author":"A. Joffe","year":"1974","unstructured":"Joffe, A.: On a set of almost deterministic k-independent random variables. Ann. Probab. 2, 161\u2013162 (1974)","journal-title":"Ann. Probab."},{"key":"9441_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/11523468_20","volume-title":"Proc. ICALP 2005","author":"M. Kowaluk","year":"2005","unstructured":"Kowaluk, M., Lingas, A.: LCA queries in directed acyclic graphs. In: Proc. ICALP 2005. Lecture Notes in Computer Science, vol. 3580, pp. 241\u2013248. Springer, Berlin (2005)"},{"key":"9441_CR20","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K., Galil, Z.: Monotone switching circuits and Boolean matrix product. In: Proc. MFCS 1975, pp.\u00a0315\u2013319 (1975)","DOI":"10.1007\/3-540-07389-2_214"},{"issue":"2","key":"9441_CR21","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/0020-0190(71)90006-8","volume":"1","author":"J.I. Munro","year":"1971","unstructured":"Munro, J.I.: Efficient determination of the transitive closure of a directed graph. Inf. Process. Lett. 1(2), 56\u201358 (1971)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9441_CR22","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0304-3975(75)90009-2","volume":"1","author":"M. Paterson","year":"1975","unstructured":"Paterson, M.: Complexity of monotone networks for Boolean matrix product. Theor. Comput. Sci. 1(1), 13\u201320 (1975)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9441_CR23","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1137\/0204027","volume":"4","author":"V.R. Pratt","year":"1975","unstructured":"Pratt, V.R.: The power of negative thinking in multiplying Boolean matrices. SIAM J. Comput. 4(3), 326\u2013330 (1975)","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"9441_CR24","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/S0019-9958(85)80024-3","volume":"67","author":"W. Rytter","year":"1985","unstructured":"Rytter, W.: Fast recognition of pushdown automaton and context-free languages. Inf. Control 67(1\u20133), 12\u201322 (1985)","journal-title":"Inf. Control"},{"key":"9441_CR25","unstructured":"Shapira, A., Yuster, R., Zwick, U.: All-pairs bottleneck paths in vertex weighted graphs. In: Proc. SODA 2007, pp.\u00a0978\u2013985 (2007)"},{"key":"9441_CR26","doi-asserted-by":"crossref","unstructured":"Seidel, R.: On the all-pairs-shortest-path problem. In: Proc. 24th Annual ACM Symposium on Theory of Computing, pp.\u00a0745\u2013749 (1992)","DOI":"10.1145\/129712.129784"},{"key":"9441_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1007\/3-540-49543-6_18","volume-title":"Randomization and Approximation Techniques in Computer Science, Second International Workshop, RANDOM\u201998","author":"C.P. Schnorr","year":"1998","unstructured":"Schnorr, C.P., Subramanian, C.R.: Almost optimal (on the average) combinatorial algorithms for Boolean matrix product witnesses, computing the diameter. In: Randomization and Approximation Techniques in Computer Science, Second International Workshop, RANDOM\u201998. Lecture Notes in Computer Science, vol. 1518, pp. 218\u2013231. Springer, Berlin (1998)"},{"key":"9441_CR28","doi-asserted-by":"crossref","unstructured":"Vassilevska Williams, V., Williams, R.: Subcubic equivalences between path, matrix, and triangle problems. In: Proc. FOCS 2010 (to appear)","DOI":"10.1109\/FOCS.2010.67"},{"key":"9441_CR29","doi-asserted-by":"crossref","unstructured":"Yuster, R., Zwick, U.: Fast sparse matrix multiplication. ACM Trans. Algorithms (TALG) 1(1) (2005). Preliminary version in Proc. ESA (2004)","DOI":"10.1145\/1077464.1077466"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9441-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9441-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9441-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T17:42:23Z","timestamp":1559670143000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9441-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9,14]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["9441"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9441-x","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9,14]]}}}