Optimal Alphabetic Ternary Trees

2014/02/13 by J. David Morgenthaler, T. C. Hu, Morgenthaler, J. David +1
Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences #cs.DS #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1402.3036

arxiv created 2014/02/13 · openalex publication_date 2014/02/13 · arxiv updated 2014/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We give a new algorithm to construct optimal alphabetic ternary trees, where every internal node has at most three children. This algorithm generalizes the classic Hu-Tucker algorithm, though the overall computational complexity has yet to be determined.

Related

• Counting ternary trees according to the number of middle edges and factorizing into (3/2)-ary trees
• A New Algorithm for Building Alphabetic Minimax Trees
• Cartesian trees and Lyndon trees
• A note on naturally embedded ternary trees
• On the Ding and Helleseth's 9th open problem about optimal ternary cyclic codes