What costs are minimized by Huffman trees?

We characterize those functions on weighted trees that are minimized at Huffman trees and those that are minimized at trees with the same level sequence as a Huffman tree. An important tool is a set of inequalities between weights of subtrees shown to be characteristic for Huffman trees. A byproduct...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on discrete mathematics 2005, Vol.19 (1), p.46-68
Main Authors: FORST, Gunnar, THORUP, Anders
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Coding, codes
Combinatorics
Combinatorics. Ordered structures
Costs
Exact sciences and technology
Graph theory
Information, signal and communications theory
Mathematics
Sciences and techniques of general use
Signal and communications theory
Telecommunications and information theory
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We characterize those functions on weighted trees that are minimized at Huffman trees and those that are minimized at trees with the same level sequence as a Huffman tree. An important tool is a set of inequalities between weights of subtrees shown to be characteristic for Huffman trees. A byproduct is an algorithm transforming an arbitrary weighted tree into a Huffman tree; for a given tree, the maximal number of steps that may be taken by this algorithm is a numerical measure of how far the tree is from being a Huffman tree.
ISSN:0895-4801
1095-7146
DOI:10.1137/S0895480103421725