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 Huffmans 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