Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property

DOI10.1006/jagm.2002.1213zbMath1005.94013OpenAlexW2033300243MaRDI QIDQ4538082

Phil Bradford, Lawrence L. Larmore, Mordecai J. Golin, Wojciech Rytter

Publication date: 11 July 2002

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: http://repository.ust.hk/ir/bitstream/1783.1-702/1/200005.pdf

zbMATH Keywords

dynamic programmingMonge matrixmonotone matrixlopsided treesHuffman codesoptimal prefix-free codes

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85) Prefix, length-variable, comma-free codes (94A45)

Related Items (4)

Dynamic Shannon coding ⋮ Computing a Hamiltonian path of minimum Euclidean length inside a simple polygon ⋮ More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding ⋮ Generalized Huffman coding for binary trees with choosable edge lengths

This page was built for publication: Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property