Abstract
Lopsided trees are rooted r-ary trees in which the length of the edge from a node to its ith child depends upon the value of i. A lopsided tree with n leaves is optimal if it has minimum esternal path length among all lopsided trees with n leaves. In this thesis we derive some new combinatorial properties of optimal lopsided trees. Knowing these properties will permit us to
⋅ Design an algorithm for constructing optimal trees that is more efficient than those previously known.
⋅ Analyze the asymptotic behavior of the cost of the optimal trees as a function of n, solving an open problem posed by Kapoor and Reingold who only analyzed the binary tree case (when r = 2).
Post a Comment