Accession Number : AD0746153
Title : Optimal Weighted Doubly-Chained Trees.
Descriptive Note : Technical rept.,
Corporate Author : CALIFORNIA INST OF TECH PASADENA DEPT OF INFORMATION SCIENCES
Personal Author(s) : Kennedy,Stephen R.
Report Date : MAY 1972
Pagination or Media Count : 27
Abstract : 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)
Descriptors : (*SEARCH THEORY, TOPOLOGY), SCHEDULING, CODING, ALGORITHMS, COMPUTER PROGRAMMING
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE