Carleton University
Technical Report TR-185
January 1991
TR-184: Uniform Generation of Combinatorial Objects in Parallel
M.D. Atkinson & J.-R. Sack
Abstract
Unbiased random generators for permutations and binary trees are developed for a PRAM. The generators are capable of generating a random permutation on n symbols or a binary tree on n nodes in time O(log n), space O(n.), with O(n) processors; they are also capable of generating various related combinatorial objects.