Parallel Construction Of Optimal Alphabetic Trees

A parallel algorithm is given which constructs an optimal alphabetic tree in O(log³ n) time with n² log n processors. The construction is basically a parallelization of the Garsia-Wachs version [5] of the Hu-tucker algorithm [8]. The best previous NC algorithm for the problem uses n 6 = log O(1) n processors. [15] Our method is an extension of techniques used first in [3] and later used in [13] for the Huffman coding problem, which can be viewed as the alphabetic tree problem for the special case of a monotone weight sequence. In this paper, we extend to the case of certain "almost monotone " sequences, which we call "sorted regular valleys." The processing of such subsequences depends on a quadrangle inequality, while the total number of global iterations depends on a kind of tree contraction. Altogether we can view our algorithmic approach as (quadrangle inequality + tree contraction). An optimal alphabetic tree is a special case of an optimal binary search tree where all..