Parallel construction of optimal alphabetic trees
Lawrence L. Larmore, Teresa M. Przytycka, Wojciech Rytter · 1993
A parallel algorithm is given which constructs an optimal alphabetic tree in 0(log3 n) time with n2 log n processors.The construction is basically a paral.lelization of the Garsia-Wachs version [5] of the Hu-tucker algorithm [8].The best previous NC algorithm for the problem uses n6/ logo(l) 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 cue 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 inegualitg + tree contraction).An optimal alphabetic tree is a special case of an optimal binary search tree where all the weights are in the leaves.Thus, the result gives a partial answer to the open problem posed in [3]: is there an NC algorithm which can find an optimal binary search tree and which U*%S 7?6-t p9%s.7.3.2iTafvr Svme G > o? " This research was supported