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

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

doi:10.1587/transfun.E96.A.1059

IEICE TRANSACTIONS on Fundamentals

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

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

Full Text Views

0

Cite this

Summary :

A non-regular tree T with a prescribed branching sequence (s₁,s₂,...,s_n) 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 s_i 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(n²) time and O(n²+nS_n-1) time, respectively, provided a preprocessing takes O(n²S_n-1) time and space in advance, where .

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E96-A No.6 pp.1059-1065

Publication Date: 2013/06/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E96.A.1059

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Authors

Ro-Yu WU
  Lunghwa University of Science and Technology
Jou-Ming CHANG
  National Taipei College of Business
An-Hang CHEN
  National Taipei College of Business
Ming-Tat KO
  Academia Sinica

Keyword

loopless algorithms, ranking algorithm, unranking algorithm, lexicographic order, Gray-code order, non-regular trees

Cite this

Copy

Ro-Yu WU, Jou-Ming CHANG, An-Hang CHEN, Ming-Tat KO, "Ranking and Unranking of Non-regular Trees in Gray-Code Order" in IEICE TRANSACTIONS on Fundamentals, vol. E96-A, no. 6, pp. 1059-1065, June 2013, doi: 10.1587/transfun.E96.A.1059.
Abstract: A non-regular tree T with a prescribed branching sequence (s₁,s₂,...,s_n) 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 s_i 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(n²) time and O(n²+nS_n-1) time, respectively, provided a preprocessing takes O(n²S_n-1) time and space in advance, where .
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E96.A.1059/_p

Copy

@ARTICLE{e96-a_6_1059,
author={Ro-Yu WU, Jou-Ming CHANG, An-Hang CHEN, Ming-Tat KO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Ranking and Unranking of Non-regular Trees in Gray-Code Order},
year={2013},
volume={E96-A},
number={6},
pages={1059-1065},
abstract={A non-regular tree T with a prescribed branching sequence (s₁,s₂,...,s_n) 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 s_i 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(n²) time and O(n²+nS_n-1) time, respectively, provided a preprocessing takes O(n²S_n-1) time and space in advance, where .},
keywords={},
doi={10.1587/transfun.E96.A.1059},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - Ranking and Unranking of Non-regular Trees in Gray-Code Order
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1059
EP - 1065
AU - Ro-Yu WU
AU - Jou-Ming CHANG
AU - An-Hang CHEN
AU - Ming-Tat KO
PY - 2013
DO - 10.1587/transfun.E96.A.1059
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E96-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2013
AB - A non-regular tree T with a prescribed branching sequence (s₁,s₂,...,s_n) 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 s_i 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(n²) time and O(n²+nS_n-1) time, respectively, provided a preprocessing takes O(n²S_n-1) time and space in advance, where .
ER -

IEICE TRANSACTIONS on Fundamentals