Optimal Weighted Doubly-Chained Trees

摘要

The problem of minimizing the weighted path length of a doubly-chained tree structure is addressed. This problem is shown to correspond to two others: a binary tree minimization problem and a certain type of machine scheduling problem. An efficient branch and bound algorithm, using a modification of Huffman's technique for weighted binary trees and observations from the equivalent problems, is presented. Finally the special case in which all weights are equal is discussed. Applications to minimum-redundancy coding problems are noted. (Author)