Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes.

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 general dimension-adjacent trees which are independent of the addresses of vertices in the -dimensional crossed cube . Based on dimension-adjacent trees and an arbitrary root vertex, a parallel algorithm with the time complexity is proposed to construct ISTs on , where . [Copyright &y& Elsevier]