Constructing trees in parallel
Mikhail J. Atallah, S. Rao Kosaraju, Lawrence L. Larmore, Glenn Miller, Shang‐Hua Teng · 1989
An O(log ~ n) time, n2/logn processor as well as an O(log n) time, n3/log n processor CREW deterministic parallel algorithms are presented for constructing Huffman codes from a given list of frequences.The time can be reduced to O(log n(loglog n) 2) on an CRCW model, using only n2/(log log n) 2 processors.Also presented is an optimal O(log n) time, O(n/log n) processor EREW parallel algorithm for constructing a tree given a list of leaf depths when the depths are monotonic.An O(log 2 n) time, n processor parallel algorithm is given for the general tree construction problem.We also give an O(log 2 n) time n2/log2n processor algorithm which finds a nearly optimal binary search tree.An O(log 2 n) time n 2'36 processor algorithm for recognizing linear context free languages is given.A crucial ingredient in achieving those bounds is a formulation of these problems as multiplications of special matrices which we call concave matrices.The structure of these matrices makes their parallel multiplication dramatically more efficient than that of arbitrary matrices.