Parallel construction of independent spanning trees and an application in diagnosis on Möbius cubes

Independent spanning trees (ISTs) on networks have applications to increase fault-tolerance, bandwidth, and security. Mobius cubes are a class of the important variants of hypercubes. A recursive algorithm to construct n ISTs on n-dimensional Mobius cube M (n) was proposed in the literature. However, there exists dependency relationship during the construction of ISTs and the time complexity of the algorithm is as high as O(NlogN), where N=2 (n) is the number of vertices in M (n) and na parts per thousand yen2. In this paper, we study the parallel construction and a diagnostic application of ISTs on Mobius cubes. First, based on a circular permutation n-1,n-2,aEuro broken vertical bar,0 and the definitions of dimension-backbone walk and dimension-backbone tree, we propose an O(N) parallel algorithm, called PMCIST, to construct n ISTs rooted at an arbitrary vertex on M (n) . Based on algorithm PMCIST, we further present an O(n) parallel algorithm. Then we provide a parallel diagnostic algorithm with high efficiency to diagnose all the vertices in M (n) by at most n+1 steps, provided the number of faulty vertices does not exceed n. Finally, we present simulation experiments of ISTs and an application of ISTs in diagnosis on 0-M (4).