Two-dimensional alphabetic trees have many applications in a wide variety of diverse fields.Despite the existense of a relatively fast algorithm that finds an approximate 2-dimensional optimal alphabetic tree(OAT),a dynamic programming approach must still be used to determine the exact solution.To apply dynamic programming ,the (OAT) can be found by examining all the nodes in the 2-d array of weights as possible roots for the optimal tree.In this paper we introduce the concept of goodness for each cut to limit the search for an optimal solution.The measure of goodness is a value we call the expense of the cut,only cuts with expense less than a given limit L are considered good cuts.At every level of the tree only the good cuts are tested as possible candidates for an optimal solution.
DIMACS Home Page