{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,6]],"date-time":"2022-12-06T05:28:23Z","timestamp":1670304503365},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1997,9]]},"abstract":"Some parallel algorithms have the property that, as they are allowed to take more time, the total work that they do is reduced. This paper describes several algorithms with this property. These algorithms solve important problems on directed graphs, including breadth-first search, topological sort, strong connectivity, and and the single source shorest path problem. All of the algorithms run on the EREW PRAM model of parallel computer, except the algorithm for strong connectivity, which runs on the probabilistic EREW PRAM.<\/jats:p>","DOI":"10.1145\/265910.265923","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"742-778","source":"Crossref","is-referenced-by-count":17,"title":["Time-work tradeoffs for parallel algorithms"],"prefix":"10.1145","volume":"44","author":[{"given":"Thomas H.","family":"Spencer","sequence":"first","affiliation":[{"name":"Univ. of Nebraska at Omaha, Omaha"}]}],"member":"320","published-online":{"date-parts":[[1997,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219025"},{"key":"e_1_2_1_2_1","volume-title":"The Design and Analysis of Computer Algorithms","author":"AHO A. V.","unstructured":"AHO , A. V. , HOPCROFT , J. E. , AND ULLMAN , J. D. 1974. The Design and Analysis of Computer Algorithms . Addison-Wesley , Reading, Mass . AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J. D. 1974. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass."},{"key":"e_1_2_1_3_1","volume-title":"Data Structures and Algorithms","author":"AHO A. V.","unstructured":"AHO , A. V. , HOPCROFT , J. E. , AND ULLMAN , J.D. 1982. Data Structures and Algorithms . Addison- Wesley , Reading, Mass . AHO, A. V., HOPCROFT, J. E., AND ULLMAN, J.D. 1982. Data Structures and Algorithms. Addison- Wesley, Reading, Mass."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321815"},{"key":"e_1_2_1_5_1","unstructured":"COHEN E. 1992. Parallel algorithm with improved work for shortest-paths from multiple sources. Manuscript. COHEN E. 1992. Parallel algorithm with improved work for shortest-paths from multiple sources. Manuscript."},{"key":"e_1_2_1_6_1","first-page":"1","volume-title":"Proceedings of the 19th Annual ACM Symposium on Theory of Computing","author":"COPPERSMITH D.","year":"1987","unstructured":"COPPERSMITH , D. , AND WINOGRAD , S. 1987 . Matrix multiplication via arithmetic progressions . In Proceedings of the 19th Annual ACM Symposium on Theory of Computing ( New York, N.Y., May 25-27). ACM, New York , pp. 1 - 6 . 10.1145\/28395.28396 COPPERSMITH, D., AND WINOGRAD, S. 1987. Matrix multiplication via arithmetic progressions. In Proceedings of the 19th Annual ACM Symposium on Theory of Computing (New York, N.Y., May 25-27). ACM, New York, pp. 1-6. 10.1145\/28395.28396"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_2_1_8_1","first-page":"240","volume-title":"Proceedings of the 16th Annual ACM Symposium on Theory of Computing (Washington, D.C., Apr. 30-May 2) ACM","author":"GALIL Z.","year":"1984","unstructured":"GALIL , Z. 1984 . Optimal parallel algorithms for string matching . In Proceedings of the 16th Annual ACM Symposium on Theory of Computing (Washington, D.C., Apr. 30-May 2) ACM , New York , pp. 240 - 248 . 10.1145\/800057.808687 GALIL, Z. 1984. Optimal parallel algorithms for string matching. In Proceedings of the 16th Annual ACM Symposium on Theory of Computing (Washington, D.C., Apr. 30-May 2) ACM, New York, pp. 240-248. 10.1145\/800057.808687"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90164-0"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(87)90062-9"},{"key":"e_1_2_1_11_1","first-page":"750","volume-title":"Proceedings of the 24th Annual ACM Symposium on Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM","author":"KLEIN P. N.","year":"1992","unstructured":"KLEIN , P. N. , AND SARIAM , S. 1992 . A parallel randomized approximation scheme for shortest paths . In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM , New York , pp. 750 - 758 . 10.1145\/129712.129785 KLEIN, P. N., AND SARIAM, S. 1992. A parallel randomized approximation scheme for shortest paths. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing (Victoria, B.C., Canada, May 4-6). ACM, New York, pp. 750-758. 10.1145\/129712.129785"},{"key":"e_1_2_1_12_1","volume-title":"The Art of Computer Programming. Volume 1: Fundamental Algorithms","author":"KNUTH D. E.","unstructured":"KNUTH , D. E. 1980. The Art of Computer Programming. Volume 1: Fundamental Algorithms . Addison-Wesley , Reading, Mass . KNUTH, D. E. 1980. The Art of Computer Programming. Volume 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass."},{"key":"e_1_2_1_13_1","volume-title":"Handbook of Theoretical Computer Science","author":"KARP R. M.","unstructured":"KARP , R. M. , AND RAMA cHAN DRAN , V. 1990. A survey of parallel algorithms for shared-memory machines . In Handbook of Theoretical Computer Science . J. van Leeuwen, ed. MIT Press, Cambridge , Mass . KARP, R. M., AND RAMAcHANDRAN, V. 1990. A survey of parallel algorithms for shared-memory machines. In Handbook of Theoretical Computer Science. J. van Leeuwen, ed. MIT Press, Cambridge, Mass."},{"key":"e_1_2_1_14_1","volume-title":"Parallel dictionaries on 2-3 trees","author":"PAUL W.","unstructured":"PAUL , W. , VISHKIN , U. , AND WAGNER , H. 1983. Parallel dictionaries on 2-3 trees . In Automata, Languages and Programming. J. Diaz, ed. pp. 597-609. PAUL, W., VISHKIN, U., AND WAGNER, H. 1983. Parallel dictionaries on 2-3 trees. In Automata, Languages and Programming. J. Diaz, ed. pp. 597-609."},{"key":"e_1_2_1_15_1","first-page":"496","volume-title":"Proceedings of the 26th Annual Symposium on the Foundations of Computer Science. IEEE","author":"REIF J.","year":"1985","unstructured":"REIF , J. 1985 . An optimal parallel algorithm for integer sorting . In Proceedings of the 26th Annual Symposium on the Foundations of Computer Science. IEEE , New York , pp. 496 - 503 . REIF, J. 1985. An optimal parallel algorithm for integer sorting. In Proceedings of the 26th Annual Symposium on the Foundations of Computer Science. IEEE, New York, pp. 496-503."},{"key":"e_1_2_1_16_1","first-page":"89","article-title":"Time-work tradeoffs for parallel algorithms","author":"SPENCER T.","year":"1989","unstructured":"SPENCER , T. 1989 . Time-work tradeoffs for parallel algorithms . Tech. Report , 89 - 26 . RPI, Troy, N.Y. SPENCER, T. 1989. Time-work tradeoffs for parallel algorithms. Tech. Report, 89-26. RPI, Troy, N.Y.","journal-title":"Tech. Report"},{"key":"e_1_2_1_17_1","first-page":"425","volume-title":"Proceedings of the 2nd Annual Symposium on Discrete Algorithms.","author":"SPENCER T.","year":"1991","unstructured":"SPENCER , T. 1991 a. Time-work tradeoffs for parallel graph algorithms . In Proceedings of the 2nd Annual Symposium on Discrete Algorithms. pp. 425 - 432 . SPENCER, T. 1991a. Time-work tradeoffs for parallel graph algorithms. In Proceedings of the 2nd Annual Symposium on Discrete Algorithms. pp. 425-432."},{"key":"e_1_2_1_18_1","first-page":"81","volume-title":"Proceedings of the 3rd Symposium on Parallel Algorithms and Architectures.","author":"SPENCER T.","year":"1991","unstructured":"SPENCER , T. 1991 b. More time-work tradeoffs for parallel graph algorithms . In Proceedings of the 3rd Symposium on Parallel Algorithms and Architectures. pp. 81 - 93 . 10.1145\/113379.113387 SPENCER, T. 1991b. More time-work tradeoffs for parallel graph algorithms. In Proceedings of the 3rd Symposium on Parallel Algorithms and Architectures. pp. 81-93. 10.1145\/113379.113387"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1137\/0201010","article-title":"Depth first search and linear graph algorithms","volume":"1","author":"TARJAN R.","year":"1972","unstructured":"TARJAN , R. 1972 . Depth first search and linear graph algorithms . SIAM J. Comput. 1 , 215 - 225 . TARJAN, R. 1972. Depth first search and linear graph algorithms. SIAM J. Comput. 1, 215-225.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1137\/0214061","article-title":"An efficient parallel biconnectivity algorithm","volume":"14","author":"TARJAN R.","year":"1985","unstructured":"TARJAN , R. , AND VISHKIN , U. 1985 . An efficient parallel biconnectivity algorithm . SIAM J. Comput. 14 , 862 - 874 . TARJAN, R., AND VISHKIN, U. 1985. An efficient parallel biconnectivity algorithm. SIAM J. Comput. 14, 862-874.","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_21_1","volume-title":"Symp. ParaL Algor. Arch. 200-209","author":"ULLMAN J.","year":"1990","unstructured":"ULLMAN , J. , AND YANNAKAKIS , M. 1990 . High-probability parallel transitive closure algorithms . Symp. ParaL Algor. Arch. 200-209 . 10.1145\/97444.97686 ULLMAN, J., AND YANNAKAKIS, M. 1990. High-probability parallel transitive closure algorithms. Symp. ParaL Algor. Arch. 200-209. 10.1145\/97444.97686"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/265910.265923","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,5]],"date-time":"2022-12-05T13:42:01Z","timestamp":1670247721000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/265910.265923"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,9]]},"references-count":21,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1997,9]]}},"alternative-id":["10.1145\/265910.265923"],"URL":"http:\/\/dx.doi.org\/10.1145\/265910.265923","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1997,9]]}}}