Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes
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 n general dimension-adjacent trees which are independent of the addresses of vertices in the n n -dimensional crossed cube CQn C Q n . Based on n n dimension-adjacent trees and an arbitrary root vertex, a parallel algorithm with the time complexity O(2n) O ( 2 n ) is proposed to construct n n ISTs on CQn C Q n , where n?1 n ? 1 .
dimension-adjacent tree parallel construction independent spanning tree crossed cube internally disjoint path