Trees with Minimum Weighted Path Length:Parallel Algorithms.

Parallel Algorithms

As a model of parallel computations we choose the Parallel Random Access Machines (PRAM), see [14].

From the point of view of parallel complexity two parameters are of

interest: parallel time (usually we require poly logarithmic time) and total work (time multiplied by the number of processors).

The sequential greedy algorithm for Huffman coding is quite simple, but unfortunately it appears to be inherently sequential. Its parallel counterpart is much more complicated, and requires a new approach. The global structure of Huffman trees must be explored in depth.

A full binary tree T is said to be left-justified if it satisfies the following properties:

1. the depths of the leaves are in non-increasing order from left to right,

2. let u be a left brother of v, and assume that the height of the subtree rooted at v is at least l. Then the tree rooted at u is full at level l, which means that u has 2l descendants at distance l.

Basic property of left-justified trees

Let T be a left-justified binary tree. Then, T consists of one leftmost branch and the subtrees hanging from this branch have logarithmic height.

LEMMA 14.9 Assume that the weights w1, w2, ..., wn are pairwise distinct and in increasing order. Then, there is Huffman tree for (w1, w2,..., wn) that is left-justified.

The left-justified trees are used together with efficient algorithm for the CLWS problem (the Concave Least Weight Subsequence problem, to be defined below) to show the following fact.

THEOREM 14.12 [3]

The parallel Huffman coding problem can be solved in polylogarithmic time with quadratic work.

Hirschberg and Larmore [16] define the Least Weight Subsequence (LWS) problem as follows: Given an integer n, and a real-valued weight function w(i, j) defined for integers 0 ≤ i < j ≤ n, find a sequence of integers α = (0 = α0 < α1 < ... < αk−1 < αk = n) such that w(α) = ),k−1 w(αi , αi+1) is minimized. Thus, the LWS problem reduces trivially toth e minimum path problem on a weighted directed acyclic graph. The Single Source LWS problem is to find such a minimal sequence 0 = α0 < α1 < ... < αk−1 < αk = m for all m ≤ n. The weight function is said to be concave if for all 0 ≤ i0 ≤ i1 < j0 ≤ j1 ≤ n,

The inequality (14.2) is also called the quadrangle inequality [52].

The LWS problem with the restriction that the weight function is concave is called the Concave Least Weight Subsequence (CLWS) problem. Hirschberg and Larmore [16] show that the LWS problem can be solved in O(n2) sequential time, while the CLWS problem can be solved in O(n log n) time. Wilber [51] gives an O(n)-time algorithm for the CLWS problem.

In the parallel setting, the CLWS problem seems to be more difficult. The best current poly logarithmic time algorithm for the CLWS problem uses concave matrix multiplication techniques and requires O(log2 n) time with n2/ log2 n processors.

Larmore and Przytycka [37] have shown how to compute efficiently CLWS in sublinear time with the total work smaller than quadratic. Using this approach they showed the following fact (which has been later slightly improved [28, 39].

THEOREM 14.13 Optimal Huffman tree can be computed in O(√n log n) time with linear number of processors.

Karpinski and Nekrich have shown an efficient parallel algorithm which approximates optimal Huffman code, see [5].

Similar, but much more complicated algorithm works for alphabetic trees. Again the CLWS algorithm is the main tool.

THEOREM 14.14 [23]

Optimal alphabetic tree can be constructed in poly logarithmic time with quadratic number of processors.

In case of general binary search trees the situation is more difficult. Poly logarithmic time algorithms need huge number of processors. However sublinear parallel time is easier.

THEOREM 14.15 [48] [31]

The OBST problem can be solved in (a) poly logarithmic time with O(n6) processors,

(b) in sublinear time and quadratic total work.