{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,18]],"date-time":"2024-07-18T02:51:37Z","timestamp":1721271097571},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1997,4,1]],"date-time":"1997-04-01T00:00:00Z","timestamp":859852800000},"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":[[1997,4]]},"DOI":"10.1007\/bf02523680","type":"journal-article","created":{"date-parts":[[2006,11,8]],"date-time":"2006-11-08T04:50:25Z","timestamp":1162961425000},"page":"399-415","source":"Crossref","is-referenced-by-count":18,"title":["Efficient parallel algorithms for computing all pair shortest paths in directed graphs"],"prefix":"10.1007","volume":"17","author":[{"given":"Yijie","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V. Y.","family":"Pan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J. H.","family":"Reif","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02523680_CR1","unstructured":"[AGM] N. Alon, Z. Galil, and O. Margalit. On the exponent of all pairs shortest path problem.Proc. 32nd Ann. IEEE Symp. FOCS, pp. 569\u2013575, 1991."},{"key":"BF02523680_CR2","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1137\/0210049","volume":"10","author":"E. Dekel","year":"1981","unstructured":"[DNS] E. Dekel, D. Nassimi, and S. Sahni. Parallel matrix and graph algorithms.SIAM J. Comput. 10:657\u2013675, 1981.","journal-title":"SIAM J. Comput."},{"key":"BF02523680_CR3","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1109\/TC.1983.1676223","volume":"32","author":"E. Dekel","year":"1983","unstructured":"[DS] E. Dekel and S. Sahni. Binary trees and parallel scheduling algorithms.IEEE Trans. Comput. 32:307\u2013315, 1983.","journal-title":"IEEE Trans. Comput."},{"key":"BF02523680_CR4","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E. W. Dijkstra","year":"1959","unstructured":"[D] E. W. Dijkstra. A note on two problems in connextion with graphs.Numer. Math. 1:269\u2013271, 1959.","journal-title":"Numer. Math."},{"key":"BF02523680_CR5","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R. N. Floyd","year":"1962","unstructured":"[Fl] R. N. Floyd. Algorithm 97, Shortest path.Comm. ACM 5:345, 1962.","journal-title":"Comm. ACM"},{"issue":"1","key":"BF02523680_CR6","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1137\/0205006","volume":"5","author":"M. L. Fredman","year":"1976","unstructured":"[Fr] M. L. Fredman. New bounds on the complexity of the shortest path problem.SIAM J. Comput. 5(1):83\u201389, 1976.","journal-title":"SIAM J. Comput."},{"issue":"1","key":"BF02523680_CR7","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0020-0190(88)90164-0","volume":"28","author":"H. Gazit","year":"1988","unstructured":"[GM] H. Gazit and G. L. Miller. An improved parallel algorithm that computes the BFS numbering of a directed graph.Inform. Process. Lett. 28(1):61\u201365, 1988.","journal-title":"Inform. Process. Lett."},{"issue":"1","key":"BF02523680_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/321992.321993","volume":"24","author":"D. B. Johnson","year":"1977","unstructured":"[J] D. B. Johnson. Efficient algorithms for shortest paths in sparse networks.J. Assoc. Comput. Mach. 24(1):1\u201313, 1977.","journal-title":"J. Assoc. Comput. Mach."},{"key":"BF02523680_CR9","series-title":"Handbook of Theoretical Computer Science","first-page":"869","volume-title":"A survey of parallel algorithms for shared memory machines","author":"M. Karp","year":"1990","unstructured":"[KR] M. Karp and V. Ramachandran. A survey of parallel algorithms for shared memory machines.Handbook of Theoretical Computer Science, pp. 869\u2013941. North-Holland, Amsterdam, 1990."},{"key":"BF02523680_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1007\/3-540-52921-7_94","volume-title":"Proc. SIGAL '90","author":"A. Lingas","year":"1990","unstructured":"[L] A. Lingas. Efficient parallel algorithms for path problems in planar directed graphs.Proc. SIGAL '90, pp. 447\u2013457. Lecture Notes in Computer Science, vol. 450. Springer-Verlag, Berlin, 1990."},{"key":"BF02523680_CR11","unstructured":"[PK] R. C. Paige and C. P. Kruskal. Parallel algorithms for shortest path problems.Proc. Internat. Conf. on Parallel Processing, St. Charles, Illinois, pp. 14\u201319, 1985."},{"key":"BF02523680_CR12","doi-asserted-by":"crossref","unstructured":"[PP1] V. Y. Pan and F. P. Preparata. Supereffective slow-down of parallel algorithms.Proc. ACM Symp. on Parallel Algorithms and Architectures, San Diego, California, pp. 402\u2013409, 1992.","DOI":"10.1145\/140901.141926"},{"issue":"4","key":"BF02523680_CR13","doi-asserted-by":"crossref","first-page":"811","DOI":"10.1137\/0224051","volume":"24","author":"V. Y. Pan","year":"1995","unstructured":"[PP2] V. Y. Pan and F. P. Preparata. Work-preserving speed-up of parallel matrix computations.SIAM J. Comput. 24(4):811\u2013821, 1995.","journal-title":"SIAM J. Comput."},{"issue":"3","key":"BF02523680_CR14","doi-asserted-by":"crossref","first-page":"494","DOI":"10.1016\/0022-0000(89)90013-5","volume":"38","author":"V. Y. Pan","year":"1989","unstructured":"[PR1] V. Y. Pan and J. H. Reif. Fast and efficient solution of path algebra problems.J. Comput. System Sci. 38(3):494\u2013510, 1989.","journal-title":"J. Comput. System Sci."},{"key":"BF02523680_CR15","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0020-0190(91)90013-8","volume":"40","author":"V. Y. Pan","year":"1991","unstructured":"[PR2] V. Y. Pan and J. H. Reif. The parallel computation of minimum cost paths in graphs by stream contraction.Inform. Process. Lett. 40:79\u201383, 1991.","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"BF02523680_CR16","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1137\/0214030","volume":"14","author":"R. Reischuk","year":"1985","unstructured":"[R] R. Reischuk. Probabilistic parallel algorithms for sorting and selection.SIAM J. Comput. 14(2):396\u2013409, 1985.","journal-title":"SIAM J. Comput."},{"key":"BF02523680_CR17","doi-asserted-by":"crossref","unstructured":"[S] R. Seidel. On the all-pair-shortest-path problem.Proc. 24th ACM STOC, pp. 745\u2013749, 1992.","DOI":"10.1145\/129712.129784"},{"key":"BF02523680_CR18","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0020-0190(92)90200-F","volume":"43","author":"T. Takaoka","year":"1992","unstructured":"[T] T. Takaoka. A new upper bound on the complexity of the all pairs shortest path problem.Inform. Process. Lett. 43:195\u2013199, 1992.","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"BF02523680_CR19","doi-asserted-by":"crossref","first-page":"348","DOI":"10.1137\/0204030","volume":"4","author":"L. G. Valiant","year":"1975","unstructured":"[V] L. G. Valiant. Parallelism in comparison problems.SIAM J. Comput. 4(3):348\u2013355, 1975.","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523680.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02523680\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02523680","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T20:39:44Z","timestamp":1558298384000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02523680"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,4]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1997,4]]}},"alternative-id":["BF02523680"],"URL":"https:\/\/doi.org\/10.1007\/bf02523680","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,4]]}}}