Fateme Ashari-Ghomi and Najme Khorasani and Abbas Nowzari-Dalini
Ranking and Unranking Algorithms for kary Trees in Gray Code Order
1020 - 1025
2012
6
8
International Journal of Computer and Information Engineering
https://publications.waset.org/pdf/9384
https://publications.waset.org/vol/68
World Academy of Science, Engineering and Technology
In this paper, we present two new ranking and unranking
algorithms for kary trees represented by xsequences in Gray
code order. These algorithms are based on a gray code generation algorithm
developed by Ahrabian et al.. In mentioned paper, a recursive
backtracking generation algorithm for xsequences corresponding to
kary trees in Gray code was presented. This generation algorithm
is based on Vajnovszkis algorithm for generating binary trees in
Gray code ordering. Up to our knowledge no ranking and unranking
algorithms were given for xsequences in this ordering. we present
ranking and unranking algorithms with O(kn2) time complexity for
xsequences in this Gray code ordering
Open Science Index 68, 2012