{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T23:41:00Z","timestamp":1783035660063,"version":"3.54.6"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540422877","type":"print"},{"value":"9783540482246","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_15","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T02:29:04Z","timestamp":1193538544000},"page":"178-189","source":"Crossref","is-referenced-by-count":15,"title":["All-Pairs Shortest Paths Computation in the BSP Model"],"prefix":"10.1007","author":[{"given":"Alexandre","family":"Tiskin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"issue":"1","key":"15_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(90)90188-N","volume":"71","author":"A. Aggarwal","year":"1990","unstructured":"A. Aggarwal, A. K. Chandra, and M. Snir. Communication complexity of PRAMs. Theoretical Computer Science, 71(1):3\u201328, March 1990.","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"15_CR2","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1006\/jcss.1997.1388","volume":"54","author":"N. Alon","year":"1997","unstructured":"N. Alon, Z. Galil, and O. Margalit. On the exponent of the all pairs shortest path problem. Journal of Computer and System Sciences, 54(2):255\u2013262, April 1997.","journal-title":"Journal of Computer and System Sciences"},{"key":"15_CR3","unstructured":"B. Carr\u00e9. Graphs and Networks. Oxford Applied Mathematics and Computer Science Series. Clarendon Press, 1979."},{"issue":"3","key":"15_CR4","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. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251\u2013280, March 1990.","journal-title":"Journal of Symbolic Computation"},{"key":"15_CR5","unstructured":"T. H. Cormen, C. E. Leiserson, and R. L. Rivest. Introduction to Algorithms. The MIT Electrical Engineering and Computer Science Series. The MIT Press and McGraw-Hill, 1990."},{"key":"15_CR6","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"E. W. Dijkstra. A note on two problems in connection with graphs. Numerische Mathematik, 1:269\u2013271, 1959.","journal-title":"Numerische Mathematik"},{"key":"15_CR7","unstructured":"I. Foster. Designing and Building Parallel Programs. Addison-Wesley, 1995."},{"key":"15_CR8","unstructured":"M. Gondran and M. Minoux. Graphs and Algorithms. Wiley\u2014Interscience Series in Discrete Mathematics. John Wiley & Sons, 1984."},{"key":"15_CR9","first-page":"147","volume":"19","author":"M. Gondran","year":"1984","unstructured":"M. Gondran and M. Minoux. Linear algebra in dioids: A survey of recent results. Annals of Discrete Mathematics, 19:147\u2013164, 1984.","journal-title":"Annals of Discrete Mathematics"},{"issue":"1","key":"15_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"D. B. Johnson","year":"1977","unstructured":"D. B. Johnson. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, 24(1):1\u201313, January 1977.","journal-title":"Journal of the ACM"},{"key":"15_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1007\/BFb0015236","volume-title":"Computer Science Today: Recent Trends and Developments","author":"W. F. McColl","year":"1995","unstructured":"W. F. McColl. Scalable computing. In J. van Leeuwen, editor, Computer Science Today: Recent Trends and Developments, volume 1000 of Lecture Notes in Computer Science, pages 46\u201361. Springer-Verlag, 1995."},{"key":"15_CR12","unstructured":"W. F. McColl. A BSP realisation of Strassen\u2019s algorithm. In M. Kara, J. R. Davy, D. Goodeve, and J. Nash, editors, Abstract Machine Models for Parallel and Distributed Computing, pages 43\u201346. IOS Press, 1996."},{"key":"15_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/3-540-61626-8_3","volume-title":"Proceedings of Euro-Par\u2019 96 (Part I)","author":"W. F. McColl","year":"1996","unstructured":"W. F. McColl. Universal computing. In L. Boug\u00e9 et al., editors, Proceedings of Euro-Par\u2019 96 (Part I), volume 1123 of Lecture Notes in Computer Science, pages 25\u201336. Springer-Verlag, 1996."},{"key":"15_CR14","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/978-3-7091-9076-0_9","volume":"7","author":"G. Rote","year":"1990","unstructured":"G. Rote. Path problems in graphs. Computing Supplementum, 7:155\u2013189, 1990.","journal-title":"Computing Supplementum"},{"key":"15_CR15","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/PL00009198","volume":"20","author":"T. Takaoka","year":"1998","unstructured":"T. Takaoka. Subcubic cost algorithms for the all pairs shortest path problem. Algorithmica, 20:309\u2013318, 1998.","journal-title":"Algorithmica"},{"issue":"1-2","key":"15_CR16","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0304-3975(97)00197-7","volume":"196","author":"A. Tiskin","year":"1998","unstructured":"A. Tiskin. The bulk-synchronous parallel random access machine. Theoretical Computer Science, 196(1-2):109\u2013130, April 1998.","journal-title":"Theoretical Computer Science"},{"key":"15_CR17","unstructured":"A. Tiskin. Bulk-synchronous parallel Gaussian elimination. In N. N. Vasil\u2019ev and A. M. Vershik, editors, Representation Theory, Dynamical Systems, Combinatorial and Algorithmic Methods (Part 4), volume 258 of Zapiski Nauchnykh Seminarov POMI. Russian Academy of Sciences, 1999. Also to appear in Journal of Mathematical Sciences."},{"issue":"8","key":"15_CR18","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"L. G. Valiant","year":"1990","unstructured":"L. G. Valiant. A bridging model for parallel computation. Communications of the ACM, 33(8):103\u2013111, August 1990.","journal-title":"Communications of the ACM"},{"key":"15_CR19","unstructured":"U. Zimmermann. Linear and Combinatorial Optimization in Ordered Algebraic Structures, volume 10 of Annals of Discrete Mathematics. North-Holland, 1981."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,24]],"date-time":"2019-02-24T14:08:11Z","timestamp":1551017291000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}