{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T05:30:38Z","timestamp":1737437438857,"version":"3.33.0"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1997,2,1]],"date-time":"1997-02-01T00:00:00Z","timestamp":854755200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int J Parallel Prog"],"published-print":{"date-parts":[[1997,2]]},"DOI":"10.1007\/bf02700044","type":"journal-article","created":{"date-parts":[[2007,9,18]],"date-time":"2007-09-18T05:24:12Z","timestamp":1190093052000},"page":"1-16","source":"Crossref","is-referenced-by-count":25,"title":["Randomized parallel list ranking for distributed memory multiprocessors"],"prefix":"10.1007","volume":"25","author":[{"given":"Frank","family":"Dehne","sequence":"first","affiliation":[]},{"given":"Siang W.","family":"Song","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF02700044_CR1","doi-asserted-by":"crossref","unstructured":"M. Reid-Miller, List Ranking and List Scan on the Cray C-90,Proc. ACM Symp. on Parallel Algorithms and Architectures, 104\u2013113 (1994).","DOI":"10.1145\/181014.181049"},{"key":"BF02700044_CR2","doi-asserted-by":"crossref","unstructured":"R. J. Anderson and L. Snyder, A Comparison of Shared and Nonshared Memory Models of Computation,Proc. of the IEEE,79(4):480\u2013487.","DOI":"10.1109\/5.92042"},{"key":"BF02700044_CR3","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1146\/annurev.cs.01.060186.001445","volume":"1","author":"L. Snyder","year":"1986","unstructured":"L. Snyder, Type Architectures, Shared Memory and the Corollary of Modest Potential,Ann. Rev. Comput. Sci.,1:289\u2013317 (1986).","journal-title":"Ann. Rev. Comput. Sci."},{"key":"BF02700044_CR4","doi-asserted-by":"crossref","unstructured":"L. G. Valiantet al., General Purpose Parallel Architectures, inHandbook of Theoretical Computer Science, J. van Leeuwen, ed., MIT Press\/Elsevier, pp. 943\u2013972 (1990).","DOI":"10.1016\/B978-0-444-88071-0.50023-0"},{"key":"BF02700044_CR5","doi-asserted-by":"crossref","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,Comm. ACM,33:103\u2013111 (1990).","journal-title":"Comm. ACM"},{"key":"BF02700044_CR6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/3-540-55706-7_1","volume":"621","author":"A. V. Gerbessiotis","year":"1992","unstructured":"A. V. Gerbessiotis and L. G. Valiant, Direct Bulk-Synchronous Parallel Algorithms,Proc. 3rd Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science,621:1\u201318 (1992).","journal-title":"Proc. 3rd Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science"},{"key":"BF02700044_CR7","doi-asserted-by":"crossref","unstructured":"F. Dehne, A. Fabri, and A. Rau-Chaplin, Scalable Parallel Geometric Algorithms for Coarse Grained Multicomputers, inProc. ACM Symp. Computational Geometry, pp. 298\u2013307 (1993).","DOI":"10.1145\/160985.161154"},{"key":"BF02700044_CR8","doi-asserted-by":"crossref","unstructured":"F. Dehne, A. Fabri, and C. Kenyon, Scalable and Architecture Independent Parallel Geometric Algorithms with High Probability Optimal Time,Proc. 6th IEEE Symposium on Parallel and Distributed Processing, pp. 586\u2013593 (1994).","DOI":"10.1109\/SPDP.1994.346119"},{"key":"BF02700044_CR9","doi-asserted-by":"crossref","unstructured":"F. Dehne, X. Deng, P. Dymond, A Fabri, and A. A. Kokhar, A Randomized Parallel 3D Convex Hull Algorithm for Coarse Grained Parallel Multicomputers,Proc ACM Symp. on Parallel Algorithms and Architectures (1995).","DOI":"10.1145\/215399.215410"},{"key":"BF02700044_CR10","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"K. Mulmuley","year":"1993","unstructured":"K. Mulmuley,Computational Geometry: An Introduction Through Randomized Algorithms, Prentice Hall, New York, (1993)."},{"key":"BF02700044_CR11","unstructured":"X. Deng and P. Dymond, Efficient Routing and Message Bounds for Optimal Parallel Algorithms,Proc. Int. Parallel Proc. Symp. (1995)."},{"key":"BF02700044_CR12","doi-asserted-by":"crossref","unstructured":"G. E. Blelloch, C. E. Leisersson, B. M. Maggs, and C. G. Plaxton, A Comparison of Sorting Algorithms for the Connection Machine CM-2,Proc. ACM Symp. on Parallel Algorithms and Architectures, pp. 3\u201316 (1991).","DOI":"10.1145\/113379.113380"},{"key":"BF02700044_CR13","doi-asserted-by":"crossref","unstructured":"X. Deng and N. Gu, Good Programming Style on Multiprocessors,Proc. IEEE Symposium on Parallel and Distributed Processing, pp. 538\u2013543 (1994).","DOI":"10.1109\/SPDP.1994.346125"},{"key":"BF02700044_CR14","doi-asserted-by":"crossref","unstructured":"X. Deng, A Convex Hull Algorithm for Coarse Grained Multiprocessors,Proc. 5th International Symposium on Algorithms and Computation (1994).","DOI":"10.1007\/3-540-58325-4_232"},{"key":"BF02700044_CR15","doi-asserted-by":"crossref","unstructured":"Hui Li and K. C. Sevcik, Parallel Sorting by Overpartitioning,Proc. ACM Symp. On Parallel Algorithms and Architectures, pp. 46\u201356 (1994).","DOI":"10.1145\/181014.192329"},{"key":"BF02700044_CR16","unstructured":"J. J\u00e0J\u00e0,An Introduction to Parallel Algorithms. Addison Wesley, 1992."},{"key":"BF02700044_CR17","unstructured":"M. Reid-Miller, C. L. Miller, and F. Modugno, List Ranking and Parallel Tree Compaction, J. H. Reif, ed.,Synthesis of Parallel Algorithms, Morgan Kaufmann Publisher (1993)."},{"key":"BF02700044_CR18","unstructured":"J. C. Wyllie, The Complexity of Parallel Computation, Technical Report TR 79-387, Department of Computer Science, Cornell University (1979)."},{"issue":"1","key":"BF02700044_CR19","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1137\/0217009","volume":"17","author":"R. Cole","year":"1988","unstructured":"R. Cole and U. Vishkin, Approximate Parallel Scheduling, Part I: the basic technique with Applications to optimal Parallel list Ranking in Logarithmic Time,SIAM J. Computing,17(1):128\u2013142 (1988).","journal-title":"SIAM J. Computing"},{"key":"BF02700044_CR20","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1007\/BFb0040376","volume":"319","author":"J. R. Anderson","year":"1988","unstructured":"J. R. Anderson and G. L. Miller, Deterministic Parallel List Ranking. InVLSI Algorithms and Architectures: 3rd Aegean Workshop on Computing, J. H. Reif, ed., AWOC\u201988, Springer Verlag, Lecture Notes in Computer Science,319:81\u201390, (1988).","journal-title":"VLSI Algorithms and Architectures: 3rd Aegean Workshop on Computing, J. H. Reif, ed., AWOC\u201988, Springer Verlag, Lecture Notes in Computer Science"},{"key":"BF02700044_CR21","first-page":"47","volume":"5","author":"G. L. Miller","year":"1989","unstructured":"G. L. Miller and J. H. Reif, Parallel Tree Contraction Part 1: Fundamentals,Advances in Computing Research,5:47\u201372 (1989).","journal-title":"Advances in Computing Research"},{"issue":"6","key":"BF02700044_CR22","doi-asserted-by":"crossref","first-page":"1128","DOI":"10.1137\/0220070","volume":"20","author":"G. L. Miller","year":"1991","unstructured":"G. L. Miller and J. H. Reif, Parallel Tree Contraction Part 1: Further Applications,SIAM J. Computing,20(6):1128\u20131147 (December 1991).","journal-title":"SIAM J. Computing"},{"issue":"5","key":"BF02700044_CR23","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0020-0190(90)90196-5","volume":"33","author":"J. R. Anderson","year":"1990","unstructured":"J. R. Anderson and G. L. Miller, A Simple Randomized Parallel Algorithm for list Ranking,Information Processing Letters,33(5):269\u2013273, (January 1990).","journal-title":"Information Processing Letters"},{"key":"BF02700044_CR24","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1016\/S0019-9958(86)80046-8","volume":"69","author":"M. J. Atallah","year":"1986","unstructured":"M. J. Atallah and S. E. Hambrusch, Solving tree problems on a Mesh-Connected Processor Array,Information and Control,69:168\u2013187, (1986).","journal-title":"Information and Control"},{"key":"BF02700044_CR25","unstructured":"S. Baase, Introduction to parallel Connectivity List Ranking, and Euler Tour Techniques,Synthesis of Parallel Algorithms, J. H. Reif, ed., Morgan Kaufmann Publisher, (1993)."}],"container-title":["International Journal of Parallel Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02700044.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02700044\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02700044","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T01:23:25Z","timestamp":1737422605000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02700044"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,2]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1997,2]]}},"alternative-id":["BF02700044"],"URL":"https:\/\/doi.org\/10.1007\/bf02700044","relation":{},"ISSN":["0885-7458","1573-7640"],"issn-type":[{"type":"print","value":"0885-7458"},{"type":"electronic","value":"1573-7640"}],"subject":[],"published":{"date-parts":[[1997,2]]}}}