{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T15:36:41Z","timestamp":1742398601388},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648482"},{"type":"electronic","value":"9783540685302"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-68530-8_33","type":"book-chapter","created":{"date-parts":[[2007,11,8]],"date-time":"2007-11-08T22:14:16Z","timestamp":1194560056000},"page":"393-404","source":"Crossref","is-referenced-by-count":23,"title":["\u0394-Stepping : A Parallel Single Source Shortest Path Algorithm"],"prefix":"10.1007","author":[{"given":"Ulrich","family":"Meyer","sequence":"first","affiliation":[]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,3,15]]},"reference":[{"issue":"4","key":"33_CR1","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/BF01408019","volume":"20","author":"P. Adamson","year":"1991","unstructured":"P. Adamson and E. Tick. Greedy partitioned algorithms for the shortest path problem. International Journal of Parallel Programming, 20(4):271\u2013298, 1991.","journal-title":"International Journal of Parallel Programming"},{"key":"33_CR2","unstructured":"R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms and Applications. Prentice Hall, 1993."},{"key":"33_CR3","unstructured":"N. Alon, J. H. Spencer, and P. Erd\u0151s. The Probabilistic Method. Wiley, 1992."},{"key":"33_CR4","doi-asserted-by":"crossref","unstructured":"G. S. Brodal, J. L. Tr\u00e4ff, and C. D. Zaroliagis. A parallel priority queue with constant time operation. In Proceedings of the 11th International Parallel Processing Symposium, pages 689\u2013693. IEEE, 1997.","DOI":"10.1109\/IPPS.1997.580979"},{"issue":"11","key":"33_CR5","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1145\/358690.358717","volume":"25","author":"K. M. Chandy","year":"1982","unstructured":"K. M. Chandy and J. Misra. Distributed computation on graphs: Shortest path algorithms. Communications of the ACM, 25(11):833\u2013837, 1982.","journal-title":"Communications of the ACM"},{"key":"33_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/BFb0027117","volume-title":"Solving Combinatorial Optimization Problem in Parallel","author":"A. Clementi","year":"1996","unstructured":"A. Clementi, J. Rolim, and E. Urland. Randomized parallel algorithms. In A. Ferreira and P. Pardalos, editors, Solving Combinatorial Optimization Problem in Parallel, volume 1054 of LNCS, pages 25\u201350. Springer, 1996."},{"key":"33_CR7","doi-asserted-by":"crossref","unstructured":"E. Cohen. Polylog-time and near-linear work approximation scheme for undirected shortest paths. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pages 16\u201326, 1994.","DOI":"10.1145\/195058.195089"},{"issue":"2","key":"33_CR8","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":"33_CR9","series-title":"Lect Notes Comput Sci","volume-title":"23rd Symposium on Mathematical Foundations of Computer Science","author":"A. Crauser","year":"1998","unstructured":"A. Crauser, K. Mehlhorn, U. Meyer, and P. Sanders. A parallelization of Dijkstra\u2019s shortest path algorithm. In 23rd Symposium on Mathematical Foundations of Computer Science, LNCS, Brno, Czech Republic, 1998. Springer."},{"key":"33_CR10","doi-asserted-by":"crossref","unstructured":"A. Crauser, K. Mehlhorn, U. Meyer, and P. Sanders. Parallelizing Dijkstra\u2019s shortest path algorithm. Technical report, MPI-Informatik, 1998. in preparation.","DOI":"10.1007\/BFb0055823"},{"key":"33_CR11","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."},{"key":"33_CR12","unstructured":"E. A. Dinic. Economical algorithms for finding shortest paths in a network. In Transportation Modeling Systems, pages 36\u201344, 1978."},{"issue":"11","key":"33_CR13","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":"33_CR14","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":"33_CR15","series-title":"Lect Notes Comput Sci","first-page":"259","volume-title":"Proceedings of Symposion on Theoretical Aspects of Computer Science (STACS\u2019 92)","author":"T. Hagerup","year":"1992","unstructured":"T. Hagerup. The log-star revolution. In A. Finkel and M. Jantzen, editors, Proceedings of Symposion on Theoretical Aspects of Computer Science (STACS\u2019 92), volume 577 of LNCS, pages 259\u2013280. Springer, Feb. 1992."},{"key":"33_CR16","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 Proceedings of the 4th Annual Symposium on Parallel Algorithms and Architectures, pages 353\u2013362. ACM Press, 1992.","DOI":"10.1145\/140901.141913"},{"issue":"4","key":"33_CR17","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":"33_CR18","unstructured":"J. J\u00e1j\u00e1. An Introduction to Parallel Algorithms. Addison-Wesley, 1992."},{"key":"33_CR19","doi-asserted-by":"crossref","unstructured":"P. N. Klein and S. Sairam. A parallel randomized approximation scheme for shortest paths. In Proc. 24th Ann. ACM Symp. on Theory of Computing, pages 750\u2013758, Victoria, B.C., Canada, 1992.","DOI":"10.1145\/129712.129785"},{"key":"33_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/3-540-61626-8_3","volume-title":"Proc. Euro-Par\u2019 96 Parallel Processing","author":"W. F. McColl","year":"1996","unstructured":"W. F. McColl. Universal computing. In L. Bouge, P. Fraigniaud, A. Mignotte, and Y. Robert, editors, Proc. Euro-Par\u2019 96 Parallel Processing, volume 1123 of LNCS, pages 25\u201336. Springer, 1996."},{"key":"33_CR21","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":"33_CR22","unstructured":"R. C. Paige and C. P. Kruskal. Parallel algorithms for shortest path problems. In International Conference on Parallel Processing, pages 14\u201320. IEEE, 1985."},{"key":"33_CR23","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"P. Raghavan. Probabilistic construction of deterministic algorithms: Approximating packing integer programs. Journal of Computer and System Sciences, 37:130\u2013143, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"33_CR24","unstructured":"M. Snir, S. W. Otto, S. Huss-Lederman, D. W. Walker, and J. Dongarra. MPI \u2014 the Complete Reference. MIT Press, 1996."},{"key":"33_CR25","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":"33_CR26","doi-asserted-by":"publisher","first-page":"1505","DOI":"10.1016\/0167-8191(95)00025-J","volume":"21","author":"J. L. Tr\u00e4ff","year":"1995","unstructured":"J. L. Tr\u00e4ff. An experimental comparison of two distributed single-source shortest path algorithms. Parallel Computing, 21:1505\u20131532, 1995.","journal-title":"Parallel Computing"},{"key":"33_CR27","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/BFb0030108","volume-title":"Irregular\u2019 96","author":"J. L. Tr\u00e4ff","year":"1996","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\u2019 96, volume 1117 of LNCS, pages 183\u2013194. Springer, 1996."},{"key":"33_CR28","doi-asserted-by":"crossref","unstructured":"L. G. Valiant. General purpose parallel architectures. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A: Algorithms and Complexity, pages 943\u2013971. Elsevier, 1990.","DOI":"10.1016\/B978-0-444-88071-0.50023-0"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA\u2019 98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-68530-8_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,4]],"date-time":"2019-05-04T08:28:10Z","timestamp":1556958490000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-68530-8_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648482","9783540685302"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-68530-8_33","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}