SIAM Journal on Computing · 1974 · 70 citations · 7 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsData StructuresCoding TheoryCombinatorial OptimizationSearching AlgorithmsBinary Search TreesDepth-first SearchHuffman CodingOptimal Prefix ComputationPrefix CodesTree Algorithms
An algorithm is given for constructing a binary tree of minimum weighted path length for n nonnegative weights under the constraint that no path length exceed a given bound L. The number of operations required is proportional to $Ln^2 $. Such problems, which impose an additional constraint on the usual Huffman tree, arise in many applications, including computer file searching and the construction of optimal prefix codes under certain practical conditions.
7
Donald E. Knuth · Acta Informatica · 1971 · 448 citations
Variable-Length Binary Encodings
E. N. Gilbert, E. F. Moore · Bell System Technical Journal · 1959 · 359 citations
Generating a canonical prefix encoding
Eugene S. Schwartz, Bruce Kallick · Communications of the ACM · 1964 · 130 citations · Full text