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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

33 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Pages (from-to)1279-1301
Journal / PublicationJournal of Supercomputing
Issue number3
Publication statusPublished - Sep 2013


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).

Research Area(s)

  • Circular permutation, Diagnosis, Independent spanning tree, Möbius cube, Nonnegative vector, Parallel algorithm

Citation Format(s)