An extended result of Kleitman and Saks concerning binary trees
In a recent paper, \textit{D. J. Kleitman} and \textit{M. E. Saks} [SIAM J. Alg. Discrete Meth. 2, 142-146 (1981; Zbl 0498.68038)] gave a proof of Huang's conjecture on alphabetic binary trees. Given a set \(E=\{e_ i\}\), \(i=0,1,2,...,m\) and assigned positive weights to its elements and supposing the elements are indexed such that \(w(e_ 0)\leq w(e_ 1)\leq...\leq w(e_ m)\), where \(w(e_ i)\) is the weight of \(e_ i\), we call the following sequence \(E^*\) a 'saw-tooth' sequence \(E^*=(e_ 0,e_ m,e_ 1,...,e_ j,e_{m-j},...)\). Huang's conjecture is: \(E^*\) is the most expensive sequence for alphabetic binary trees. This paper shows that this property is true for the L-restricted alphabetic binary trees, where L is the maximum length of the leaves and \(\lceil \log_ 2(m+1)\rceil \leq L\leq m\).
scientific article; zbMATH DE number 3905858