Parallel construction of independent spanning trees and an application in diagnosis on Mobius 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 Moebius 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(N log N), where N = 2~n is the number of vertices in M_n and n ≥ 2. 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, ...,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 O-M_4.