On the Huffman and alphabetic tree problem with general cost functions

DOI10.1007/S00453-013-9755-6MaRDI QIDQ2249740zbMATH OpenOpenAlexFDO

Authors Hiroshi Fujiwara, Tobias Jacobs

Publication date 3 July 2014

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://soar-ir.repo.nii.ac.jp/record/19568/files/On_the_Huffman_and_Alphabetic_Tree_Problem_with_General_Cost_Functions.pdf

zbMATH Keywords

alphabetic treebinary treedynamic programmingHuffman codingmulti-ary treeoptimal tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Recommendations

• On the Huffman and alphabetic tree problem with general cost functions
• scientific article; zbMATH DE number 4031716
• scientific article; zbMATH DE number 68566
• Optimal alphabetic binary tree for a nonregular cost function
• The Optimal Alphabetic Tree Problem Revisited
• The Optimal Alphabetic Tree problem revisited
• On the convex hull of Huffman trees
• Generalized Huffman coding for binary trees with choosable edge lengths
• Publication:3027031
• Huffman coding with letter costs: a linear-time approximation scheme

Cites work

• A Fast Algorithm For Optimum Height-Limited Alphabetic Binary Trees
• A Method for the Construction of Minimum-Redundancy Codes
• A New Algorithm for Minimum Cost Binary Trees
• A New Proof of the T-C Algorithm
• Algorithms – ESA 2005
• Alphabetic coding with exponential costs
• Approximating Decision Trees with Multiway Branches
• Approximating Optimal Binary Decision Trees
• Binary Trees Optimum Under Various Criteria
• Correctness of constructing optimal alphabetic trees revisited
• Decision trees for entity identification, approximation algorithms and hardness results
• Greedy splitting algorithms for approximating multiway partition problems
• Height Restricted Optimal Binary Trees
• scientific article; zbMATH DE number 432778 (Why is no real title available?)
• scientific article; zbMATH DE number 437543 (Why is no real title available?)
• scientific article; zbMATH DE number 4210044 (Why is no real title available?)
• scientific article; zbMATH DE number 5764837 (Why is no real title available?)
• On the complexity of searching in trees: average-case minimization
• Optimal alphabetic search trees with restricted maximal height
• Optimal Alphabetic Trees
• Optimal Binary Search Trees with Restricted Maximal Depth
• Optimal Computer Search Trees and Variable-Length Alphabetical Codes
• Optimal Multi-Way Search Trees
• Optimum binary search trees
• Searching in random partially ordered sets
• Should static search trees ever be unbalanced?

Cited in

(10)

• Minimal Huffman trees
• Operations research applications of dichotomous search
• Generalized Huffman coding for binary trees with choosable edge lengths
• On the Huffman and alphabetic tree problem with general cost functions
• scientific article; zbMATH DE number 4031716 (Why is no real title available?)
• On the linear description of the Huffman trees polytope
• What Costs Are Minimized by Huffman Trees?
• Partial alphabetic trees
• Old and new results on alphabetic codes
• Optimal alphabetic binary tree for a nonregular cost function

This page was built for publication: On the Huffman and alphabetic tree problem with general cost functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2249740)