Generalized Huffman coding for binary trees with choosable edge lengths

• Study of binary trees with choosable edge length, motivated by VLSI design.
• First algorithm with polynomial running time for this problem.
• Using combinatorial observations to achieve the polynomial running time.
• The algorithm is a generalization/variant of Huffman coding.

In this paper we study binary trees with choosable edge lengths, in particular rooted binary trees with the property that the two edges leading from every non-leaf to its two children are assigned integral lengths l1l1 and l2l2 with l1+l2=kl1+l2=k for a constant k∈Nk∈N. The depth of a leaf is the total length of the edges of the unique root-leaf-path.We present a generalization of Huffman coding that can decide in polynomial time if for given values d1,…,dn∈N≥0d1,…,dn∈N≥0 there exists a rooted binary tree with choosable edge lengths with n   leaves having depths at most d1,…,dnd1,…,dn.