The search functionality is under construction.

Keyword Search Result

[Keyword] loopless algorithms(1hit)

1-1hit
  • Ranking and Unranking of Non-regular Trees in Gray-Code Order

    Ro-Yu WU  Jou-Ming CHANG  An-Hang CHEN  Ming-Tat KO  

     
    PAPER

      Vol:
    E96-A No:6
      Page(s):
    1059-1065

    A non-regular tree T with a prescribed branching sequence (s1,s2,...,sn) is a rooted and ordered tree such that its internal nodes are numbered from 1 to n in preorder and every internal node i in T has si children. Recently, Wu et al. (2010) introduced a concise representation called RD-sequences to represent all non-regular trees and proposed a loopless algorithm for generating all non-regular trees in a Gray-code order. In this paper, based on such a Gray-code order, we present efficient ranking and unranking algorithms of non-regular trees with n internal nodes. Moreover, we show that the ranking algorithm and the unranking algorithm can be run in O(n2) time and O(n2+nSn-1) time, respectively, provided a preprocessing takes O(n2Sn-1) time and space in advance, where .