George Markowsky, Robert Endre Tarjan
Discrete Mathematics
Given a sequence of positive weights, W=w1≧...≧wn>0, there is a Huffman tree, T↑ ("T-up") which minimizes the following functions: max{d(wi)}; Σd(wi); Σf(d(wi)) wi(here d(wi) represents the distance of a leaf of weight wi to the root and f is a function defined for nonnegative integers having the property that g(x) = f(x + 1) - f(x) is monotone increasing) over the set of all trees for W having minimal expected length. Minimizing the first two functions was first done by Schwartz [5]. In the case of codes where W is a sequence of probabilities, this implies that the codes based on T↑ have all their absolute central moments minimal. In particular, they are the least variance codes which were also described by Kou [3]. Furthermore, there exists a Huffman tree T↓, ("T-down") which maximizes the functions considered above. However, if g(x) is monotone decreasing, T↑ and T↓, respectively maximize and minimize Σf(d(wi) wi) over the set of all trees for W having minimal expected length. In addition, we derive a number of interesting results about the distribution of labels within Huffman trees. By suitable modifications of the usual Huffman tree construction, (see [1]) T↑ and T↓ can also be constructed in time O(n log n). © 1981 Springer-Verlag.
George Markowsky, Robert Endre Tarjan
Discrete Mathematics
George Markowsky, Andrew Wohlgemuth
Discrete Applied Mathematics
Ashok K. Chandra, Lawrence T. Kou, et al.
Acta Informatica
Alfredo DeSantis, George Markowsky, et al.
FOCS 1988