Optimal Weighted Doubly-Chained Trees.

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)

Document Details

Document Type
Technical Report
Publication Date
May 01, 1972
Accession Number
AD0746153

Entities

People

  • Stephen R. Kennedy

Organizations

  • California Institute of Technology

Tags

DTIC Thesaurus Topics

  • Acquisition
  • Algorithms
  • Data Acquisition
  • Digital Information
  • Engineering
  • Observation
  • Redundancy
  • Scheduling (Production)
  • Trees (Data Structures)

Readers

  • Computer Programming and Software Development.
  • Operations Research