期刊
JOURNAL OF SUPERCOMPUTING
卷 65, 期 3, 页码 1279-1301出版社
SPRINGER
DOI: 10.1007/s11227-013-0883-1
关键词
Mobius cube; Independent spanning tree; Parallel algorithm; Nonnegative vector; Diagnosis; Circular permutation
类别
资金
- National Natural Science Foundation of China [61170021]
- Specialized Research Fund for the Doctoral Program of Higher Education [20103201110018]
- Application Foundation Research of Suzhou of China [SYG201240]
- Program for Postgraduates Research Innovation in University of Jiangsu Province [CXZZ11_0100]
- Qing Lan Project
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).
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据