کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
7543085 | 1489160 | 2011 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Ranking and unranking of non-regular trees with a prescribed branching sequence
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
سایر رشته های مهندسی
کنترل و سیستم های مهندسی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Ranking and unranking of non-regular trees with a prescribed branching sequence Ranking and unranking of non-regular trees with a prescribed branching sequence](/preview/png/7543085.png)
چکیده انگلیسی
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).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Mathematical and Computer Modelling - Volume 53, Issues 5â6, March 2011, Pages 1331-1335
Journal: Mathematical and Computer Modelling - Volume 53, Issues 5â6, March 2011, Pages 1331-1335
نویسندگان
Ro-Yu Wu, Jou-Ming Chang, Chir-Ho Chang,