{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,6,12]],"date-time":"2023-06-12T16:14:21Z","timestamp":1686586461469},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,1,12]],"date-time":"2013-01-12T00:00:00Z","timestamp":1357948800000},"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":[[2014,6]]},"DOI":"10.1007\/s00453-012-9742-3","type":"journal-article","created":{"date-parts":[[2013,1,11]],"date-time":"2013-01-11T10:51:42Z","timestamp":1357901502000},"page":"431-442","source":"Crossref","is-referenced-by-count":5,"title":["On Minimum Witnesses for Boolean Matrix Multiplication"],"prefix":"10.1007","volume":"69","author":[{"given":"Keren","family":"Cohen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raphael","family":"Yuster","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,1,12]]},"reference":[{"issue":"4","key":"9742_CR1","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(4), 434\u2013449 (1996)","journal-title":"Algorithmica"},{"key":"9742_CR2","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/978-3-540-70575-8_10","volume-title":"Proceedings of the 35th International Colloquium on Automata, Languages and Programming","author":"G.E. Blelloch","year":"2008","unstructured":"Blelloch, G.E., Vassilevska, V., Williams, R.: A new combinatorial approach for sparse graph problems. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming, pp. 108\u2013120. Springer, Berlin (2008)"},{"issue":"1","key":"9742_CR3","doi-asserted-by":"crossref","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. 13(1), 42\u201349 (1997)","journal-title":"J. Complex."},{"issue":"3","key":"9742_CR4","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(3), 251\u2013280 (1990)","journal-title":"J. Symb. Comput."},{"issue":"1\u20132","key":"9742_CR5","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)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9742_CR6","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/070695149","volume":"39","author":"A. Czumaj","year":"2009","unstructured":"Czumaj, A., Lingas, A.: Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication. SIAM J. Comput. 39(2), 431\u2013444 (2009)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"9742_CR7","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1006\/jcom.1993.1014","volume":"9","author":"Z. Galil","year":"1993","unstructured":"Galil, Z., Margalit, O.: Witnesses for boolean matrix multiplication and for transitive closure. J. Complex. 9(2), 201\u2013221 (1993)","journal-title":"J. Complex."},{"key":"9742_CR8","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 multiplication and applications. J. Complex. 14, 257\u2013299 (1998)","journal-title":"J. Complex."},{"key":"9742_CR9","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1007\/11523468_20","volume-title":"Proceedings of the 32nd International Colloquium on Automata, Languages and Programming","author":"M. Kowaluk","year":"2005","unstructured":"Kowaluk, M., Lingas, A.: LCA queries in directed acyclic graphs. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, pp. 241\u2013248. Springer, Berlin (2005)"},{"issue":"3","key":"9742_CR10","doi-asserted-by":"crossref","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. J. Comput. Syst. Sci. 51(3), 400\u2013403 (1995)","journal-title":"J. Comput. Syst. Sci."},{"key":"9742_CR11","first-page":"978","volume-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"A. Shapira","year":"2007","unstructured":"Shapira, A., Yuster, R., Zwick, U.: All-pairs bottleneck paths in vertex weighted graphs. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 978\u2013985. Society for Industrial and Applied Mathematics, Philadelphia (2007)"},{"issue":"4","key":"9742_CR12","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V. Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numer. Math. 13(4), 354\u2013356 (1969)","journal-title":"Numer. Math."},{"issue":"3","key":"9742_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1798596.1798597","volume":"6","author":"V. Vassilevska","year":"2010","unstructured":"Vassilevska, V., Williams, R., Yuster, R.: Finding heaviest h-subgraphs in real weighted graphs, with applications. ACM Trans. Algorithms 6(3), 1\u201323 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"9742_CR14","first-page":"887","volume-title":"Proceedings of the 44th Symposium on Theory of Computing","author":"V. Vassilevska Williams","year":"2012","unstructured":"Vassilevska Williams, V.: Multiplying matrices faster than coppersmith-winograd. In: Proceedings of the 44th Symposium on Theory of Computing, pp. 887\u2013898. ACM Press, New York (2012)"},{"issue":"3","key":"9742_CR15","doi-asserted-by":"crossref","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. J. ACM 49(3), 289\u2013317 (2002)","journal-title":"J. ACM"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9742-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9742-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9742-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:11Z","timestamp":1559123111000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9742-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,12]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["9742"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9742-3","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,12]]}}}