کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872930 | 1440626 | 2018 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Constructing independent spanning trees with height n on the n-dimensional crossed cube
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Independent spanning trees (ISTs) on networks have applications in reliable broadcasting, reliable communication protocols, secure message distribution. Towards the ISTs on crossed cubes, although several results have been obtained, the maximum height of the ISTs on the n-dimensional crossed cube CQn is no less than n+1 for nâ¥3. So we have the question whether there exist multiple ISTs with height lower than n+1 on CQn. In this paper, firstly, we present the construction of nâ2 ISTs rooted at node 0 on CQn, the maximum height of which is no more than n for nâ¥4. A parallel algorithm with the time complexity O(N) is also presented, where N=2n. Secondly, we present a binary XOR operation to transform the above nâ2 ISTs into the nâ2 ISTs rooted at any node that is similar to 0 on CQn. Thirdly, we revise the recursive algorithm CIST from Cheng et al. (2013) to construct nâ2 ISTs rooted at any node on CQn with the maximal height n, where the time complexity is O(Nlog2N). We have also extended the efficient parallel method to locally twisted cubes.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Future Generation Computer Systems - Volume 87, October 2018, Pages 404-415
Journal: Future Generation Computer Systems - Volume 87, October 2018, Pages 404-415
نویسندگان
Baolei Cheng, Jianxi Fan, Qiang Lyu, Jingya Zhou, Zhao Liu,