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.
| Original language | English |
|---|---|
| Pages (from-to) | 641-652 |
| Journal | Journal of Parallel and Distributed Computing |
| Volume | 73 |
| Issue number | 5 |
| Online published | 30 Jan 2013 |
| DOIs | |
| Publication status | Published - May 2013 |
Research Keywords
- Crossed cube
- Independent spanning tree
- Internally disjoint path
- Dimension-adjacent tree
- Parallel construction
Fingerprint
Dive into the research topics of 'Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver