Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes
Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Pages (from-to) | 641-652 |
| Journal / Publication | Journal of Parallel and Distributed Computing |
| Volume | 73 |
| Issue number | 5 |
| Online published | 30 Jan 2013 |
| Publication status | Published - May 2013 |
Link(s)
Abstract
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 n general dimension-adjacent trees which are independent of the addresses of vertices in the n-dimensional crossed cube CQn. Based on n dimension-adjacent trees and an arbitrary root vertex, a parallel algorithm with the time complexity O(2n) is proposed to construct n ISTs on CQn, where n ≥ 1.
Research Area(s)
- Crossed cube, Independent spanning tree, Internally disjoint path, Dimension-adjacent tree, Parallel construction
Citation Format(s)
Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes. / Cheng, Baolei; Fan, Jianxi; Jia, Xiaohua et al.
In: Journal of Parallel and Distributed Computing, Vol. 73, No. 5, 05.2013, p. 641-652.Research output: Journal Publications and Reviews (RGC: 21, 22, 62) › 21_Publication in refereed journal › peer-review
