SPACE-TIME TRADE-OFFS IN THE RELATIVE UNRANKING OF BINARY-TREES

The set of binary trees with n internal vertices can be totally ordere d using a number of different representations. There are C-n binary tr ees in any such order where C-n denotes the nth Catalan number. Given a total order on the set of binary trees with n internal vertices acid an integer i, 1 less than or equal to i less than or equal to C-n, th e unranking problem is to generate the binary tree whose ordinal numbe r is i. Given a binary tree with T with ordinal number j < C-n and an integer i, 1 less than or equal to i less than or equal to C-n - j, a slight generalization of the unranking problem, called the relative un ranking problem, is to find the binary tree with ordinal number i rela tive to T. The relative unranking problem is motivated by its applicat ion to computing a Steiner minimal tree in parallel. In this paper, a computationally efficient algorithm for solving the relative unranking problem is presented. The algorithm is based on a certain directed gr aph, called the feasible suffix graph, whose combinatorial properties are of independent interest. One of the salient features of the algori thm is that the unranking time can be traded for space. Computational experience with the algorithm is reported.