Parallel generation of í-ary trees with ballot-sequences

Abstract

We present an adaptive and cost-optimal parallel algorithm for generating t-ary trees represented by extended Ballot-sequences. This algorithm is a parallel version of a sequential generation algorithm that we discuss it first. Our parallel algorithm generates t-ary trees in B-order and can be executed on an EREW SM SIMD model.

Keywords:

• t-ary trees
• parallel algorithm
• B-order
• ballot-sequences