{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T00:41:54Z","timestamp":1768524114054,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540648277","type":"print"},{"value":"9783540685326","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055823","type":"book-chapter","created":{"date-parts":[[2006,8,17]],"date-time":"2006-08-17T13:36:31Z","timestamp":1155821791000},"page":"722-731","source":"Crossref","is-referenced-by-count":65,"title":["A parallelization of Dijkstra's shortest path algorithm"],"prefix":"10.1007","author":[{"given":"A.","family":"Crauser","sequence":"first","affiliation":[]},{"given":"K.","family":"Mehlhorn","sequence":"additional","affiliation":[]},{"given":"U.","family":"Meyer","sequence":"additional","affiliation":[]},{"given":"P.","family":"Sanders","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,28]]},"reference":[{"key":"70_CR1","unstructured":"N. Alon, J. H. Spencer, and P. Erd\u00f6s. The Probabilistic Method. Wiley, 1992."},{"key":"70_CR2","unstructured":"L. Arge. Efficient external-memory data structures and applications. PhD thesis, University of Aarhus, BRICS-DS-96-3, 1996."},{"key":"70_CR3","unstructured":"G. S. Brodal, J. L. Tr\u00e4ff, and C. D. Zaroliagis. A parallel priority queue with constant time operation. In 11th IPPS, pages 689\u2013693. IEEE, 1997."},{"key":"70_CR4","doi-asserted-by":"crossref","unstructured":"A. Clementi, L. Ku\u010dera, and J. D. P. Rolim. A randomized parallel search strategy. In A. Ferreira and J. D. P. Rolim, editors, Parallel Algorithms for Irregular Problems: State of the Art, pages 213\u2013227. Kluwer, 1994.","DOI":"10.1007\/978-1-4757-6130-6_11"},{"key":"70_CR5","doi-asserted-by":"crossref","unstructured":"E. Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. In 26th STOC, pages 16\u201326. ACM, 1994.","DOI":"10.1145\/195058.195089"},{"issue":"2","key":"70_CR6","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1006\/jagm.1996.0048","volume":"21","author":"E. Cohen","year":"1996","unstructured":"E. Cohen. Efficient parallel shortest-paths in digraphs with a separator decomposition. Journal of Algorithms, 21(2):331\u2013357, 1996.","journal-title":"Journal of Algorithms"},{"key":"70_CR7","doi-asserted-by":"crossref","unstructured":"A. Crauser, K. Mehlhorn, U. Meyer, and P. Sanders. Parallelizing Dijkstra's shortest path algorithm. Technical report, MPI-Informatik, 1998. in preparation.","DOI":"10.1007\/BFb0055823"},{"key":"70_CR8","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. Dijkstra","year":"1959","unstructured":"E. Dijkstra. A note on two problems in connexion with graphs. Num. Math., 1:269\u2013271, 1959.","journal-title":"Num. Math."},{"issue":"11","key":"70_CR9","doi-asserted-by":"publisher","first-page":"1343","DOI":"10.1145\/50087.50096","volume":"31","author":"J. R. Driscoll","year":"1988","unstructured":"J. R. Driscoll, H. N. Gabow, R. Shrairman, and R. E. Tarjan. Relaxed heaps: An alternative to Fibonacci heaps with applications to parallel computation. Communications of the ACM, 31(11):1343\u20131354, 1988.","journal-title":"Communications of the ACM"},{"key":"70_CR10","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/0166-218X(85)90059-9","volume":"10","author":"A. Frieze","year":"1985","unstructured":"A. Frieze and G. Grimmett. The shortest-path problem for graphs with random arc-lengths. Discrete Appl. Math., 10:57\u201377, 1985.","journal-title":"Discrete Appl. Math."},{"key":"70_CR11","doi-asserted-by":"crossref","unstructured":"Y. Han, V. Pan, and J. Reif. Efficient parallel algorithms for computing all pairs shortest paths in directed graphs. In 4th SPAA, pages 353\u2013362. ACM, 1992.","DOI":"10.1145\/140901.141913"},{"issue":"4","key":"70_CR12","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. On shortest paths in graphs with random weights. Math. Oper. Res., 10(4):557\u2013564, 1985.","journal-title":"Math. Oper. Res."},{"key":"70_CR13","unstructured":"J. J\u00e1j\u00e1. An Introduction to Parallel Algorithms. Addison-Wesley, 1992."},{"key":"70_CR14","doi-asserted-by":"crossref","unstructured":"R. M. Karp. The transitive closure of a random digraph. Rand. Struct. Alg., 1, 1990.","DOI":"10.1002\/rsa.3240010106"},{"key":"70_CR15","volume-title":"The Stanford GraphBase: a platform for combinatorial computing","author":"D. E. Knuth","year":"1993","unstructured":"D. E. Knuth. The Stanford GraphBase: a platform for combinatorial computing. Addison-Wesley, New York, NY, 1993."},{"key":"70_CR16","doi-asserted-by":"crossref","unstructured":"V. Kumar and E. J. Schwabe. Improved algorithms and data structures for solving graph problems in external memory. In 8th SPDP, pages 169\u2013177. IEEE, 1996.","DOI":"10.1109\/SPDP.1996.570330"},{"key":"70_CR17","doi-asserted-by":"crossref","unstructured":"U. Meyer and P. Sanders. \u03b4-stepping: A parallel shortest path algorithm. In 6th ESA, LNCS. Springer, 1998.","DOI":"10.1007\/3-540-68530-8_33"},{"key":"70_CR18","doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. H. Reif. Parallel tree contraction and its application. In 26th Symposium on Foundations of Computer Science, pages 478\u2013489. IEEE, 1985.","DOI":"10.1109\/SFCS.1985.43"},{"key":"70_CR19","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1006\/jpdc.1998.1429","volume":"49","author":"P. Sanders","year":"1998","unstructured":"P. Sanders. Randomized priority queues for fast parallel access. Journal Parallel and Distributed Computing, 49:86\u201397, 1998.","journal-title":"Journal Parallel and Distributed Computing"},{"key":"70_CR20","doi-asserted-by":"crossref","unstructured":"M. Thorup. Undirected single source shortest paths in linear time. In 38th Annual Symposium on Foundations of Computer Science, pages 12\u201321. IEEE, 1997.","DOI":"10.1109\/SFCS.1997.646088"},{"key":"70_CR21","doi-asserted-by":"crossref","unstructured":"J. L. Tr\u00e4ff and C. D. Zaroliagis. A simple parallel algorithm for the single-source shortest path problem on planar digraphs. In Irregular' 96, volume 1117 of LNCS, pages 183\u2013194. Springer, 1996.","DOI":"10.1007\/BFb0030108"},{"key":"70_CR22","unstructured":"J. S. Vitter and E. A. M. Shriver. Algorithms for parallel memory I: Two-level memories. Technical Report CS-90-21, Brown University, 1990."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1998"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055823","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T14:44:36Z","timestamp":1555771476000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055823"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648277","9783540685326"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/bfb0055823","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998]]}}}