Ranking and unranking trees with given degree sequences

In this paper, we provide algorithms to rank and unrank certain degree-restricted classes of Cayley trees. Specifically, we consider classes of trees that have a given degree sequence or a given multiset of degrees. Using special properties of a bijection due to Eğecioğlu and Remmel [3], we show that one can reduce the problem of ranking and unranking these classes of degree-restricted trees to corresponding problems of ranking and unranking certain classes of set partitions. If the underlying set of trees have n vertices, then the largest ranks involved in each case are of order n! so that it takes O(nlog(n) bits just to write down the ranks. Our ranking and unranking algorithms for these degree-restricted classes are as efficient as can be expected since we show that they require O(n2log(n) bit operations if the underlying trees have n vertices.