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