Alphabetic Minimax Trees
David G. Kirkpatrick, Maria M. Klawe · SIAM Journal on Computing · 1985
This paper concerns the following problem. Given vertices $v_1 , \cdots ,v_n $ with weights $w_1 , \cdots ,w_n $, construct a t-ary tree with leaves $v_1 , \cdots ,v_n $ in left to right order, such that if $l_i $ denotes the length of the path from $v_i $ to the root for each i, the maximum of $w_i + l_i $ is minimized. A linear algorithm is presented for the case where all the weights are integers, and this is used to obtain an $O(n\log n)$ algorithm for the case of general weights. Moreover it is shown that the minimax value obtained is bounded above by $2 + \log _t (\sum {t^{(w_i )} } )$. This result has applications in the study of the effect of fan-out constraints in logical circuits.