A Combinatorial Approach to Golomb Trees

Given a set of weights, the problem of finding the binary-tree with minimum weighted external-path length is very well understood. It can be solved using Huffman Encoding. The problem of finding such an (infinite) tree, with minimal path-length for an infinite set of weights, is not nearly as well studied. Twenty years ago Gallager and Van Voorhis described such trees for the case in which the infinite set of weights is a geometric series. These trees are now known as Golomb trees. In this talk we expand upon their results.