A WORK-TIME TRADE-OFF IN PARALLEL COMPUTATION OF HUFFMAN TREES AND CONCAVE LEAST WEIGHT SUBSEQUENCE PROBLEM
Christos Levcopoulos, Teresa M. Przytycka · Parallel Processing Letters · 1994
We present a parallel algorithm for the Concave Least Weight Subsequence (CLWS) problem that exhibits the following work-time trade-off: Given a parameter p, the algorithm runs in [Formula: see text] time using p processors. By a known reduction of the Huffman Tree problem to the CLWS problem, we obtain the same complexity bounds for the Huffman Tree problem. However, as we show, for the later problem there exists a simpler (and, in fact, slightly better) algorithm that exhibits a similar trade-off: Namely, for a given parameter p, p≥1, the algorithm runs in [Formula: see text] time using p processors.