{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:16:13Z","timestamp":1781259373542,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540542339","type":"print"},{"value":"9783540475163","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54233-7_151","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:38:07Z","timestamp":1330209487000},"page":"405-416","source":"Crossref","is-referenced-by-count":21,"title":["Fast parallel generation of random permutations"],"prefix":"10.1007","author":[{"given":"Torben","family":"Hagerup","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"31_CR1","doi-asserted-by":"crossref","unstructured":"Albers, S., and Hagerup, T. (1991), Improved Parallel Integer Sorting without Concurrent Writing, manuscript.","DOI":"10.1145\/103418.103452"},{"key":"31_CR2","doi-asserted-by":"crossref","unstructured":"Anderson, R. J. (1990), Parallel Algorithms for Generating Random Permutations on a Shared Memory Machine, in Proc. 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 95\u2013102.","DOI":"10.1145\/97444.97674"},{"key":"31_CR3","doi-asserted-by":"crossref","unstructured":"Berkman, O., and Vishkin, U. (1989), Recursive *-Tree Parallel Data-Structure, in Proc. 30th Annual Symposium on Foundations of Computer Science, pp. 196\u2013202.","DOI":"10.1109\/SFCS.1989.63478"},{"key":"31_CR4","doi-asserted-by":"crossref","unstructured":"Berkman, O., J\u00e1J\u00e1, J., Krishnamurthy, S., Thurimella, R., and Vishkin, U. (1990), Some Triply-Logarithmic Parallel Algorithms, in Proc. 31st Annual Symposium on Foundations of Computer Science, pp. 871\u2013881.","DOI":"10.1109\/FSCS.1990.89611"},{"key":"31_CR5","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1137\/0218014","volume":"18","author":"G. Bilardi","year":"1989","unstructured":"Bilardi, G., and Nicolau, A. (1989), Adaptive Bitonic Sorting: An Optimal Parallel Algorithm for Shared-Memory Machines, SIAM J. Comput.18, pp. 216\u2013228.","journal-title":"SIAM J. Comput."},{"key":"31_CR6","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/3-540-51498-8_9","volume":"380","author":"B. S. Chlebus","year":"1989","unstructured":"Chlebus, B. S., Diks, K., Hagerup, T., and Radzik, T. (1989), New Simulations between CRCW PRAMs, in Proc. 7th International Conference on Fundamentals of Computation Theory, Springer Lecture Notes in Computer Science, Vol. 380, pp. 95\u2013104.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"31_CR7","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1146\/annurev.cs.03.060188.001313","volume":"3","author":"D. Eppstein","year":"1988","unstructured":"Eppstein, D., and Galil, Z. (1988), Parallel Algorithmic Techniques for Combinatorial Computation, Ann. Rev. Comput. Sci.3, pp. 233\u2013283.","journal-title":"Ann. Rev. Comput. Sci."},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"Grolmusz, V., and Ragde, P. (1987), Incomparability in Parallel Computation, in Proc. 28th Annual Symposium on Foundations of Computer Science, pp. 89\u201398.","DOI":"10.1109\/SFCS.1987.34"},{"key":"31_CR9","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/0020-0190(89)90138-5","volume":"33","author":"T. Hagerup","year":"1989","unstructured":"Hagerup, T., and R\u00fcb, C. (1989), Optimal Merging and Sorting on the EREW PRAM, Inform. Proc. Lett.33, pp. 181\u2013185.","journal-title":"Inform. Proc. Lett."},{"key":"31_CR10","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","volume":"33","author":"T. Hagerup","year":"1990","unstructured":"Hagerup, T., and R\u00fcb, C. (1990), A Guided Tour of Chernoff Bounds, Inform. Proc. Lett.33, pp. 305\u2013308.","journal-title":"Inform. Proc. Lett."},{"key":"31_CR11","volume-title":"The Probabilistic Analysis of Combinatorial Algorithms, class notes","author":"R. M. Karp","year":"1988","unstructured":"Karp, R. M. (1988), The Probabilistic Analysis of Combinatorial Algorithms, class notes, Univ. California, Berkeley."},{"key":"31_CR12","doi-asserted-by":"crossref","first-page":"942","DOI":"10.1109\/TC.1983.1676138","volume":"32","author":"C. P. Kruskal","year":"1983","unstructured":"Kruskal, C. P. (1983), Searching, Merging, and Sorting in Parallel Computation, IEEE Trans. Comput.32, pp. 942\u2013946.","journal-title":"IEEE Trans. Comput."},{"key":"31_CR13","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/BF01840376","volume":"5","author":"C. P. Kruskal","year":"1990","unstructured":"Kruskal, C. P., Rudolph, L., and Snir, M. (1990), Efficient Parallel Algorithms for Graph Problems, Algorithmica5, pp. 43\u201364.","journal-title":"Algorithmica"},{"key":"31_CR14","doi-asserted-by":"crossref","unstructured":"Matias, Y., and Vishkin, U. (1991), Converting High Probability into Nearly-Constant Time \u2014 with Applications to Parallel Hashing, preliminary version. Also in Proc. 23rd Annual ACM Symposium on Theory of Computing, to appear.","DOI":"10.1145\/103418.103453"},{"key":"31_CR15","doi-asserted-by":"crossref","unstructured":"Miller, G. L., and Reif, J. H. (1985), Parallel Tree Contraction and Its Application, in Proc. 26th Annual Symposium on Foundations of Computer Science, pp. 478\u2013489.","DOI":"10.1109\/SFCS.1985.43"},{"key":"31_CR16","doi-asserted-by":"crossref","first-page":"744","DOI":"10.1007\/BFb0032071","volume":"443","author":"P. Ragde","year":"1990","unstructured":"Ragde, P. (1990), The Parallel Simplicity of Compaction and Chaining, in Proc. 17th International Colloquium on Automata, Languages and Programming, Springer Lecture Notes in Computer Science, Vol. 443, pp. 744\u2013751.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"31_CR17","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1137\/0218041","volume":"18","author":"S. Rajasekaran","year":"1989","unstructured":"Rajasekaran, S., and Reif, J. H. (1989), Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms, SIAM J. Comput.18, pp. 594\u2013607.","journal-title":"SIAM J. Comput."},{"key":"31_CR18","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/3-540-53487-3_42","volume":"472","author":"R. Raman","year":"1990","unstructured":"Raman, R. (1990), The Power of Collision: Randomized Parallel Algorithms for Chaining and Integer Sorting, in Proc. 10th Conference on Foundations of Software Technology and Theoretical Computer Science, Springer Lecture Notes in Computer Science, Vol. 472, pp. 161\u2013175.","journal-title":"Springer Lecture Notes in Computer Science"},{"key":"31_CR19","doi-asserted-by":"crossref","unstructured":"Reif, J. H. (1985), An Optimal Parallel Algorithm for Integer Sorting, in Proc. 26th Annual Symposium on Foundations of Computer Science, pp. 496\u2013504.","DOI":"10.1109\/SFCS.1985.9"},{"key":"31_CR20","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/356689.356692","volume":"9","author":"R. Sedgewick","year":"1977","unstructured":"Sedgewick, R. (1977), Permutation Generation Methods, Comp. Surv.9, pp. 137\u2013164.","journal-title":"Comp. Surv."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54233-7_151.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:53:16Z","timestamp":1605646396000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54233-7_151"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540542339","9783540475163"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-54233-7_151","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991]]}}}