Parallel Generation of P-sequences


We present a cost-optimal and adaptive parallel algorithm for generating t-ary trees with P-sequences. The computational model employed in this algorithm is an exclusive read exclusive write with a shared memory single instruction multiple data computer. Our parallel algorithm is the ?rst designed P-sequence generation on this model. Prior to the discussion of this parallel algorithm, a new sequential algorithm for generation of t-ary trees with P-sequences in O(1) constant average time per sequence is presented.