کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6872930 1440626 2018 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Constructing independent spanning trees with height n on the n-dimensional crossed cube
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Constructing independent spanning trees with height n on the n-dimensional crossed cube
چکیده انگلیسی
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
نویسندگان
, , , , ,