کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4949726 | 1440204 | 2017 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A parallel algorithm for constructing independent spanning trees in twisted cubes
ترجمه فارسی عنوان
الگوریتم موازی برای ساخت درختان مستقل در محوطه پیچ خورده
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های موازی، مستقل درختان درختی، شبکه های اتصال مکعب های پیچ خورده،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A long-standing conjecture mentions that a k-connected graph G admits k independent spanning trees (ISTs for short) rooted at an arbitrary node of G. An n-dimensional twisted cube, denoted by TQn, is a variation of hypercube with connectivity n and has many features superior to those of hypercube. Yang (2010) first proposed an algorithm to construct n edge-disjoint spanning trees in TQn for any odd integer n⩾3 and showed that half of them are ISTs. At a later stage, Wang et al. (2012) inferred that the above conjecture in affirmative for TQn by providing an O(NlogN) time algorithm to construct n ISTs, where N=2n is the number of nodes in TQn. However, this algorithm is executed in a recursive fashion and thus is hard to be parallelized. In this paper, we revisit the problem of constructing ISTs in twisted cubes and present a non-recursive algorithm. Our approach can be fully parallelized to make the use of all nodes of TQn as processors for computation in such a way that each node can determine its parent in all spanning trees directly by referring its address and tree indices in O(logN) time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 219, 11 March 2017, Pages 74-82
Journal: Discrete Applied Mathematics - Volume 219, 11 March 2017, Pages 74-82
نویسندگان
Jou-Ming Chang, Ting-Jyun Yang, Jinn-Shyong Yang,