{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:32:45Z","timestamp":1725485565747},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540651420"},{"type":"electronic","value":"9783540495437"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49543-6_18","type":"book-chapter","created":{"date-parts":[[2007,6,7]],"date-time":"2007-06-07T02:58:05Z","timestamp":1181185085000},"page":"218-231","source":"Crossref","is-referenced-by-count":8,"title":["Almost Optimal (on the average) Combinatorial Algorithms for Boolean Matrix Product Witnesses, Computing the Diameter (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"C. P.","family":"Schnorr","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C. R.","family":"Subramanian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1999,6,11]]},"reference":[{"key":"18_CR1","unstructured":"D. Aingworth, C. Chekuri, P. Indyk and R. Motwani, \u201cFast Estimation of Diameter and Shortest Paths (without Matrix Multiplication)\u201d, Proceedings of the Seventh Annual ACM Symposium on Discrete Algorithms, pp. 547\u2013554, 1996."},{"key":"18_CR2","doi-asserted-by":"crossref","unstructured":"N. Alon, Z. Galil, O. Margalit and M. Naor, \u201cWitnesses for Boolean Matrix Multiplication and Shortest Paths\u201d, Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, pp.417\u2013426, October 1992.","DOI":"10.1109\/SFCS.1992.267748"},{"key":"18_CR3","doi-asserted-by":"publisher","first-page":"434","DOI":"10.1007\/BF01940874","volume":"16","author":"N. Alon","year":"1996","unstructured":"N. Alon and M. Naor, \u201cDerandomization, Witnesses for Boolean Matrix Multiplication and Construction of Perfect hash functions\u201d, Algorithmica, 16:434\u2013449, 1996.","journal-title":"Algorithmica"},{"key":"18_CR4","unstructured":"N. Alon and J. Spencer, The Probabilistic Method, John Wiley & Sons, 1992."},{"key":"18_CR5","first-page":"487","volume":"194","author":"V.L. Arlazarov","year":"1970","unstructured":"V.L. Arlazarov, E.A. Dinic, M.A. Kronrod and L.A. Faradzev, \u201cOn economical construction of the transitive closure of a directed graph\u201d, Doklady Acad. Nauk SSSR, 194:487\u2013488, 1970 (in Russian).","journal-title":"Doklady Acad. Nauk SSSR"},{"key":"18_CR6","unstructured":"J. Basch, S. Khanna and R. Motwani, \u201cOn Diameter Verification and Boolean Matrix Multiplication\u201d, Technical Report, Stanford University CS department, 1995."},{"key":"18_CR7","volume-title":"Random Graphs","author":"B. Bollobas","year":"1985","unstructured":"B. Bollobas, Random Graphs, Academic Press (London), 1985."},{"key":"18_CR8","first-page":"295","volume":"60","author":"F.R.K. Chung","year":"1987","unstructured":"F.R.K. Chung, \u201cDiameters of Graphs: Old Problems and New Results\u201d, Congressus Numerantium, 60:295\u2013317, 1987.","journal-title":"Congressus Numerantium"},{"issue":"3","key":"18_CR9","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","volume":"9","author":"D. Coppersmith","year":"1990","unstructured":"D. Coppersmith and S. Winograd, \u201cMatrix multiplication via arithmetic progressions\u201d, Journal of Symbolic Computation, 9(3):251\u2013280, 1990.","journal-title":"Journal of Symbolic Computation"},{"key":"18_CR10","unstructured":"Z. Galil and O. Margalit, \u201cWitnesses for Boolean Matrix Multiplication and Shortest Paths\u201d, Journal of Complexity, pp. 417\u2013426, 1993."},{"issue":"4","key":"18_CR11","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1287\/moor.10.4.557","volume":"10","author":"R. Hassin","year":"1985","unstructured":"R. Hassin and E. Zemel, \u201cOn Shortest Paths in Graphs with Random Weights\u201d, Mathematics of Operations Research, Vol.10, No.4, 1985, 557\u2013564.","journal-title":"Mathematics of Operations Research"},{"key":"18_CR12","unstructured":"M. Karonski, \u201cRandom Graphs\u201d, Chapter 6, Handbook of Combinatorics, Vol. I, ed. Graham, Gr\u00f6tschel, Lov\u00e1szi, North-Holland, pp.351\u2013380, 1995."},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"C.J.H. McDiarmid, \u201cOn the method of bounded differences\u201d, Surveys in Combinatorics, Edited by J. Siemons, London Mathematical Society Lecture Notes Series 141, pp.148\u2013188, 1989.","DOI":"10.1017\/CBO9781107359949.008"},{"key":"18_CR14","doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.","DOI":"10.1017\/CBO9780511814075"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"C.P. Schnorr, \u201cComputation of the Boolean Matrix-Vector AND\/OR-Product in Average Time O(m + n(log n))\u201d, Informatik-Festschrift zum 60. Geburtstag von G\u00fcnter Hotz, (eds. Buchmann\/ Ganzinger\/ Paul), Teubner-Texte zur Informatik Band 1, 1992, pp.359\u2013362.","DOI":"10.1007\/978-3-322-95233-2_21"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"R. Seidel, \u201cOn the All-Pairs-Shortest-Path Problem\u201d, Proceedings of the 24th ACM Symposium on Theory of Computing, 745\u2013749, 1992.","DOI":"10.1145\/129712.129784"},{"key":"18_CR17","unstructured":"A. Srinivasan, \u201cScheduling and load-balancing via randomization\u201d, Proceedings of the FST&TCS\u201997 Pre-conference Workshop on Randomized Algorithms, Kharagpur, India, December, 1997."}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49543-6_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T19:45:51Z","timestamp":1556480751000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49543-6_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540651420","9783540495437"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-49543-6_18","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}