کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
432744 | 689058 | 2013 | 12 صفحه PDF | دانلود رایگان |
Independent spanning trees (ISTs) have increasing applications in fault-tolerance, bandwidth, and security. In this paper, we study the problem of parallel construction of ISTs on crossed cubes. We first propose the definitions of dimension-adjacent walk and dimension-adjacent tree along with a dimension property of crossed cubes. Then, we consider the parallel construction of ISTs on crossed cubes. We show that there exist nn general dimension-adjacent trees which are independent of the addresses of vertices in the nn-dimensional crossed cube CQnCQn. Based on nn dimension-adjacent trees and an arbitrary root vertex, a parallel algorithm with the time complexity O(2n)O(2n) is proposed to construct nn ISTs on CQnCQn, where n≥1n≥1.
► We propose the definitions of dimension-adjacent walk and dimension-adjacent tree.
► We present a dimension property of crossed cubes, which is vital to the IST problem.
► We give an O(2n)O(2n) parallel algorithm to construct nn ISTs rooted at any vertex on CQnCQn.
► All vertices in CQnCQn can be classified as a category with respect to the IST problem.
Journal: Journal of Parallel and Distributed Computing - Volume 73, Issue 5, May 2013, Pages 641–652