检索结果-内蒙古大学图书馆

Improved algorithms for ranking and unranking (k, m)-ary trees in B-order

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第3期44卷 1495-1510页

作者： Chang, Yu-Hsuan Wu, Ro-Yu Chang, Ruay-Shiung Chang, Jou-ming Natl Taipei Univ Business Inst Informat & Decis Sci Taipei Taiwan Lunghwa Univ Sci & Technol Dept Ind Management Taoyuan Taiwan

Du and Liu (Eur J Comb 28:1312-1321, 2007) introduced (k, m)-ary trees as a generalization of k-ary trees. In a (k, m)-ary tree, every node on even level has degree k (i.e., has k children), and every node on odd level has degree m (which is called a crucial node) or is a leaf. In particular, a (k, m)-ary tree of order n has exactly n crucial nodes. Recently, Amani and Nowzari-Dalini (Bull Iranian Math Soc 45(4):1145-1158, 2019) presented a generation algorithm to produce all (k, m)-ary trees of order n in B-order using Zaks' encoding, and showed that the generated ordering of this encoding results in a reverse-lexicographical ordering. They also proposed the corresponding ranking and unranking algorithms for (k, m)-ary trees according to such a generated ordering. These algorithms take O(kmn(2)) time and space for building a precomputed table in which (k, m)-Catalan numbers (i.e., a kind of generalized Catalan numbers) are stored in advance. Then, each ranking and unranking algorithm can be performed subsequently in O(n) and O(n log n) time, respectively. In this paper, we revisit the ranking and unranking problems. With the help of an encoding scheme called "right-distance" introduced by Wu et al. (Math Comput Model 53:1331-1335, 2011a;IEICE Trans Inf Syst E94-D:226-232, 2011b), we propose new ranking and unranking algorithms for (k, m)-ary trees of order n in B-order using Zaks' encoding. We show that both algorithms can be improved in O(kmn) time and O(n) space without building the precomputed table.

关键词： (k, m)-Ary trees ranking/unranking algorithms Zaks' sequences RD-sequences Lexicographic/reverse-lexicographic order Amortized cost

来源：评论

学校读者我要写书评

暂无评论

Improved algorithms for ranking and unranking (k, m)-Ary Trees 1

引用

13th International Conference on Algorithmic Aspects in Information and Management (AAIM)

作者： Chang, Yu-Hsuan Wu, Ro-Yu Chang, Ruay-Shiung Chang, Jou-Ming Natl Taipei Univ Business Inst Informat & Decis Sci Taipei Taiwan Lunghwa Univ Sci & Technol Dept Ind Management Taoyuan Taiwan

ISBN: (数字)9783030271954

ISBN: (纸本)9783030271954;9783030271947

Du and Liu (2007) introduced (k, m)-ary trees as a generalization of k-ary trees. In a (k, m)-ary tree, every node on even level has degree k (i.e., has k children), and every node on odd level has degree m (which is called a crucial node) or is a leaf. In particular, a (k, m)-ary tree of order n has exactly n crucial nodes. Recently, Amani and Nowzari-Dalini (2019) presented a generation algorithm to produce all (k, m)-ary trees of order n in B-order using Zaks' encoding, and show that the generated ordering of this encoding results in a reverse-lexicographical ordering. They also proposed the corresponding ranking and unranking algorithms for (k, m)-ary trees according to such a generated ordering. These algorithms take O(kmn(2)) time and space for building a precomputed table in which (k, m)-Catalan numbers (i.e., a kind of generalized Catalan numbers) are stored in advance. In this paper, we revisit the ranking and unranking problems. With the help of an encoding scheme called "right-distance" introduced by Wu et al. (2011), we propose new ranking and unranking algorithms for (k, m)-ary trees of order n in B-order using Zaks' encoding. We show that both algorithms can be improved in O(kmn) time and O(n) space without building the precomputed table.

关键词： (k, m)-ary trees ranking/unranking algorithms Zaks' sequences RD-sequences Lexicographic/Reverse-lexicographic order Amortized cost

来源：评论

学校读者我要写书评

暂无评论

Efficient reconfiguration algorithms of de Bruijn and Kautz networks into linear arrays

引用

THEORETICAL COMPUTER SCIENCE 2001年第1-2期263卷 173-189页

作者： Harbane, R Heydemann, MC Univ Paris 11 LRI UMR CNRS F-91405 Orsay France

In this paper, we prove the existence of ranking and unranking algorithms on d-ary de Bruijn and Kautz graphs. A ranking algorithm takes as input the label of a node and returns the rank r of that node in a hamiltonian path (0 less than or equal to r less than or equal to N - 1, where N is the order of the considered graph). An unranking algorithm takes as input an integer r (0 less than or equal to r less than or equal to N - 1) and returns the label of the rth ranked node in a hamiltonian path. Our results generalize results given by Annexstein for binary de Bruijn graphs. The key of our framework is based on a recursive construction of hamiltonian paths in de Bruijn and Kautz graphs. The construction uses suitable uniform homomorphisms of de Bruijn and Kautz graphs of diameter D on de Bruijn graphs of diameter D - 1. Our ranking and unranking algorithms have sequential time complexity in O(D-2), where D is the length of node labels. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： de Bruijn graph Kautz graph uniform homomorphism Hamiltonian path ranking/unranking algorithms

来源：评论

学校读者我要写书评

暂无评论

ranking and unranking of non-regular trees with a prescribed branching sequence

引用

MATHEMATICAL AND COMPUTER MODELLING 2011年第5-6期53卷 1331-1335页

作者： Wu, Ro-Yu Chang, Jou-Ming Chang, Chir-Ho Natl Taipei Coll Business Inst Informat & Decis Sci Taipei Taiwan Lunghwa Univ Sci & Technol Dept Ind Management Tao Yuan Taiwan

Ordered trees are called non-regular trees with a prescribed branching sequence (or non-regular trees for short) if their internal nodes have a pre-specified degree sequence in preorder list. This article presents two main results. First, we develop a simple algorithm to generate all non-regular trees in lexicographic order using RD-sequences defined by [R.-Y. Wu, J.-M. Chang, Y.-L. Wang, Loopless generation of non-regular trees with a prescribed branching sequence, The Computer Journal 53 (2010) 661-666]. Then, by analyzing the structure of a coding tree, this algorithm is proved to run in constant amortized time. Next, we propose efficient ranking algorithm (i.e., determining the rank of a given non-regular tree in such an order) and unranking algorithm (i.e., converting a positive integer to its corresponding RD-sequence). (C) 2010 Elsevier Ltd. All rights reserved.

关键词： Non-regular trees Enumeration algorithms ranking/unranking algorithms Constant amortized time

来源：评论

学校读者我要写书评

暂无评论

Amortized efficiency of generation, ranking and unranking left-child sequences in lexicographic order

引用

DISCRETE APPLIED MATHEMATICS 2019年 268卷 223-236页

作者： Pai, Kung-Jui Chang, Jou-Ming Wu, Ro-Yu Chang, Shun-Chieh Ming Chi Univ Technol Dept Ind Engn & Management New Taipei Taiwan Natl Taipei Univ Business Inst Informat & Decis Sci Taipei Taiwan Lunghwa Univ Sci & Technol Dept Ind Management Taoyuan Taiwan Cybersecur Technol Inst Inst Informat Ind Taipei Taiwan Saim Univ Int Sino Coll Bangkok Thailand

A new type of sequences called left-child sequences (LC-sequences for short) was recently introduced by Wu et al. (2014) for representing binary trees. They pointed out that such sequences have a natural interpretation from the view point of data structure and gave a characterization of them. Based on this characterization, there is an easily implementing algorithm that uses generate-and-test approach to filter all LC-sequences of binary trees with n internal nodes in lexicographic order, while in general it is not efficient at all. In this paper, we first design two novel rotations that allow us to drastically alter the shape of binary trees (and thus their corresponding LC-sequences). As an application, these operations can be employed to generate all LC-sequences in lexicographic order. Accordingly, we present a more efficient algorithm associated with the new types of rotations for generating all LC-sequences and show that it takes only constant amortized running cost. Moreover, we extend our study to the ranking and unranking problems. By integrating a measure called "left distances" introduced by Makinen (1987) to represent binary trees, we develop efficient ranking and unranking algorithms for LC-sequences in lexicographic order. With the help of aggregate analysis, we show that both ranking and unranking algorithms can be run in amortized cost of O(n) time and space. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Binary trees Left-child sequences Generation algorithms ranking/unranking algorithms Lexicographic order Amortized cost

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：