局部扭立方体上若干性质的研究
|
摘要
高性能并行计算机是一个国家综合科技实力的体现,在科研、教育、石油、气象等相关领域发挥着日益重要的作用。在并行处理领域,研究并行计算机系统中处理器或者处理机连接的方式(互连网络)是一个很重要的课题。一个互连网络可以用一个简单图G=(V,E)来表示,其中V代表顶点集合,而E代表边集。互连网络拓扑结构的性质对于并行计算机的性能至关重要。
互连网络的一个重要性能指标是其它己存在的网络拓扑结构能否嵌入该网络。图嵌入问题描述如下：给定一个主图G2=(V2,E2)和一个客图G1=(V1,E1),将客图G1嵌入到主图G2中就是找到G1中的每个顶点到G2中一个顶点的一个单射,以及G1中的每条边到G2中某一条路径的映射。衡量嵌入效率的两个重要指标是扩张(Dilation)和膨胀(Expansion)。性能良好的互连网络作为主图时应该具有理想的嵌入能力,从而能够使客图上的并行算法在其上能够高效地迁移并运行。
随着互连网络规模的增大,互连网络中的处理器(处理机)或通信链路出现故障的可能性也随之变大。当故障发生时,我们需要找到故障并修复它。系统级故障诊断就是识别发生故障的处理器(处理机)或通信链路的过程。系统级故障诊断可以在不增加额外投入的情况下,提高系统的可靠性和可用性。系统级故障诊断按照测试策略可分为非自适应性诊断和自适应性诊断。在自适应性诊断中,测试分配是根据之前的测试结果动态分配的,这种方式比非自适应性诊断增加了诊断的效率,可避免不必要的测试。
图的直径是图中任意两个顶点之间最短路径的最大值。直径是衡量网络通信性能的一个重要指标,它决定了任意顶点对间最大的通信延迟。根据图的直径的定义,我们可知,当删除边或者增加边时,可能会影响顶点之间的距离,进而影响图的直径。其中,删除边可以表示边故障的情形。互连网络直径的改变可以影响其通信性能,因此研究删除边或者增加边对图直径的影响是一个有意义的课题。
超立方体是一种研究较多、总体性质较好的互连网络拓扑结构。局部扭立方体(Locally Twisted Cube)是超立方体的一种重要变型,它是超立方体的强有力的竞争者,其直径约为超立方体的一半。令LT Qn表示n维局部扭立方体。
本文研究局部扭立方体中的以下几个内容：网孔嵌入性,树嵌入性,自适应性诊断和删除边或增加边时直径的改变问题。
1.本文证明了局部扭立方体具有很好的网孔嵌入性质：
(1)对于任意的整数n≥1,一个2×2n-1的网孔可以扩张1和膨胀1嵌入LTQn。
(2)对于任意的整数n≥4,两个4×2n-3的顶点互不相交网孔可以扩展1和膨胀2嵌入LTQn。
(3)对于任意的整数n≥3,一个4×(2n-2-1)网孔可以扩张2嵌入LTQn。
前两个结果在扩张方面是最优的,因为其扩张为1。2×2n-1网孔嵌入的膨胀为1,因此该嵌入在膨胀方面也是最优的。此外,对于任意的整数p≥1和q≥1,本文还给出了局部扭立方体中2p×2q网孔嵌入的分析。
2.本文证明了局部扭立方体具有很好的树嵌入性质：
(1)对于任意的整数n≥2,一棵具有2n-1个顶点的完全二叉树可以扩张2嵌入LTQn。
(2)对于任意的整数n≥1,LTQn中以任意顶点为根可以扩张1嵌入k阶二项树Bk(k为整数,且0≤k≤n)。
3.本文研究了局部扭立方体的自适应性诊断：
本文证明对于任意的整数n≥3,LTQn在至多n个顶点出错的情况下,可以在至多4轮并行测试中被自适应性诊断。然后,本文给出了LTQn的自适应性诊断算法描述及其分析。
4.本文研究了删除边或增加边时直径的改变问题,得到了以下3个结论：
(1)对于任意的整数n≥2,我们找到了使LTQn直径变大,至少需要删除的边数(用ch-(LTQn)表示)。对于n=2,n=3和任意的奇数n≥7,ch-(LTQn)=1。对于n=5和n=6,ch-(LTQn)=n-1。对于n=4和任意的偶数n≥8,ch-(LTQn)=2。
(2)对于任意的整数n≥2,当使LTQn直径变大至少需要删除的边被删除时,我们找到了LTQn直径的增加值(用diam+(LT Qn)表示),diam+(LT Qn)=1。
(3)对于任意的整数n≥4,使LTQn直径减小,至少需要增加边的上界为2n-1。
High performance parallel computers are becoming more and more important in the ar-eas of scientific research, education, petroleum, meteorology and so on. In the parallel com-puting domain, it is an important research topic to study the connection pattern(interconnection network) of processors or process computer units in the parallel computer system. An inter-connection network can be represented by a simple graph G=(V, E), where V represents the vertex set and E represents the edge set. The topology properties of interconnection networks are important to the performance of parallel computers.
One of the critical performance factors of interconnection network is whether other existing networks can be embedded into this one. This can be modeled by the following graph embedding problem:given a host graph G2=(V2, E2) and a guest graph G1=(V1, E1), which represent the network where other networks are to be embedded and the network to be embedded, respectively. The problem becomes finding an injective mapping from each node of G1to a node of G2, and a mapping from each edge of G1to a path in G2. Two common measures of the embedding efficiency are dilation and expansion. A good interconnection network is supposed to possess ideal graph embedding ability as host graph, such that parallel algorithms in guest graphs can be migrated and executed on this network efficiently.
When the system scale becomes bigger, the faulty probability of the processors or links in the system becomes higher. When the fault occurs, we need to find the fault and repair it. The fault location is a more difficult problem. System-level fault diagnosis is to find the faulty processors or links. System-level fault diagnosis can improve the system reliability and usability without adding extra system input costs. System-level fault diagnosis can be divided into non-adaptive diagnosis and adaptive diagnosis by the test strategy. In adaptive diagnosis, the test allocations are dynamically decided by the previous test results, which can increase the efficiency of diagnosis compared to the non-adaptive diagnosis, and avoid the unnecessary tests.
The diameter of a graph is the maximum value of the shortest path length between any two nodes in graph. One of the critical performance factors of an interconnection network is the diameter, which determines the maximum communication time between any pair of nodes. By the definition of graph diameter, we know that deleting edges from a graph or adding edges to a graph may affect the distance between nodes, and then the diameter of the graph will be changed, where deleting edges can denote the scenario of edge faults. The change of graph diameter can affect its communication performance, thus, it is a meaningful topic to study the diameter variability arising from the deletion of edges or the addition of edges in a graph.
The hypercube network Qn has been proved to be one of the most popular interconnec-tion networks. The locally twisted cube is an important variant of hypercube. It has many attractive features as compared to the hypercube, for instance, the diameter is only about half of that of Qn. Let LT Qn denote the n-dimensional locally twisted cube.
This thesis will study the following properties of the locally twisted cube:mesh em-bedding property, tree embedding property, adaptive diagnosis problem and the diameter variability problem arising from the deletion of edges or the addition of edges. The major contributions are listed as follows.
1. The locally twisted cube is proved to have good mesh embedding property:
(1) For any integer n≥1, a2x2n-1mesh can be embedded in LTQn with dilation1and expansion1.
(2) For any integer n≥4, two node-disjoint4x2n-3meshes can be embedded in LTQn with dilation1and expansion2.
(3) For any integer n≥3, a4x (2n-2-1) mesh can be embedded in LTQn with dilation2.
The first two results are optimal in the sense that the dilations of all embeddings are1. The embedding of the2x2n-1mesh is also optimal in terms of expansion. We also present the analysis of2p x2q mesh embedding in locally twisted cubes.
2. The locally twisted cube is proved to have good tree embedding property:
(1) For any integer n≥2, we show that a complete binary tree with2n-1nodes can be embedded into LTQn with dilation2.
(2) For any integer n≥1, a binomial tree Bk(0≤k≤n) can be embedded into LTQn with any node as its root with dilation1.
3. Adaptive diagnosis in the locally twisted cube is studied in this thesis.
This thesis proves that for any integer n≥3, LTQn can be adaptively diagnosed using at most4parallel testing rounds, with at most n faulty nodes. The proof and algorithm description of adaptive diagnosis in LTQn also have been proposed.
4. Diameter variability problems arising from the deletion of edges and addition of edges in LTQn are investigated. Three results are obtained about diameter variability prob-lems:
(1) For any integer n≥2, we find the least number of edges (denoted by ch-(LT Qn)), whose deletion from LT Qn causes the diameter to increase. For n=2,n=3and any odd integer with n≥7, ch-(LTQn)=1. For any integer with n=5and n=6, ch-(LTQn)=n-1. For n=4and any even integer with n≥8, ch-(LTQn)=2.
(2) For any integer n≥2, we find the exact augmentation value of the diameter of LTQn, when edges(ch-(LTQn)) are deleted from LTQn(denoted by diam+(LTQn)), diam+(LTQn)=1.
(3) For any integer n≥4, the least number of edges whose addition to LTQn will decrease the diameter is at most2n-1.
互连网络的一个重要性能指标是其它己存在的网络拓扑结构能否嵌入该网络。图嵌入问题描述如下：给定一个主图G2=(V2,E2)和一个客图G1=(V1,E1),将客图G1嵌入到主图G2中就是找到G1中的每个顶点到G2中一个顶点的一个单射,以及G1中的每条边到G2中某一条路径的映射。衡量嵌入效率的两个重要指标是扩张(Dilation)和膨胀(Expansion)。性能良好的互连网络作为主图时应该具有理想的嵌入能力,从而能够使客图上的并行算法在其上能够高效地迁移并运行。
随着互连网络规模的增大,互连网络中的处理器(处理机)或通信链路出现故障的可能性也随之变大。当故障发生时,我们需要找到故障并修复它。系统级故障诊断就是识别发生故障的处理器(处理机)或通信链路的过程。系统级故障诊断可以在不增加额外投入的情况下,提高系统的可靠性和可用性。系统级故障诊断按照测试策略可分为非自适应性诊断和自适应性诊断。在自适应性诊断中,测试分配是根据之前的测试结果动态分配的,这种方式比非自适应性诊断增加了诊断的效率,可避免不必要的测试。
图的直径是图中任意两个顶点之间最短路径的最大值。直径是衡量网络通信性能的一个重要指标,它决定了任意顶点对间最大的通信延迟。根据图的直径的定义,我们可知,当删除边或者增加边时,可能会影响顶点之间的距离,进而影响图的直径。其中,删除边可以表示边故障的情形。互连网络直径的改变可以影响其通信性能,因此研究删除边或者增加边对图直径的影响是一个有意义的课题。
超立方体是一种研究较多、总体性质较好的互连网络拓扑结构。局部扭立方体(Locally Twisted Cube)是超立方体的一种重要变型,它是超立方体的强有力的竞争者,其直径约为超立方体的一半。令LT Qn表示n维局部扭立方体。
本文研究局部扭立方体中的以下几个内容：网孔嵌入性,树嵌入性,自适应性诊断和删除边或增加边时直径的改变问题。
1.本文证明了局部扭立方体具有很好的网孔嵌入性质：
(1)对于任意的整数n≥1,一个2×2n-1的网孔可以扩张1和膨胀1嵌入LTQn。
(2)对于任意的整数n≥4,两个4×2n-3的顶点互不相交网孔可以扩展1和膨胀2嵌入LTQn。
(3)对于任意的整数n≥3,一个4×(2n-2-1)网孔可以扩张2嵌入LTQn。
前两个结果在扩张方面是最优的,因为其扩张为1。2×2n-1网孔嵌入的膨胀为1,因此该嵌入在膨胀方面也是最优的。此外,对于任意的整数p≥1和q≥1,本文还给出了局部扭立方体中2p×2q网孔嵌入的分析。
2.本文证明了局部扭立方体具有很好的树嵌入性质：
(1)对于任意的整数n≥2,一棵具有2n-1个顶点的完全二叉树可以扩张2嵌入LTQn。
(2)对于任意的整数n≥1,LTQn中以任意顶点为根可以扩张1嵌入k阶二项树Bk(k为整数,且0≤k≤n)。
3.本文研究了局部扭立方体的自适应性诊断：
本文证明对于任意的整数n≥3,LTQn在至多n个顶点出错的情况下,可以在至多4轮并行测试中被自适应性诊断。然后,本文给出了LTQn的自适应性诊断算法描述及其分析。
4.本文研究了删除边或增加边时直径的改变问题,得到了以下3个结论：
(1)对于任意的整数n≥2,我们找到了使LTQn直径变大,至少需要删除的边数(用ch-(LTQn)表示)。对于n=2,n=3和任意的奇数n≥7,ch-(LTQn)=1。对于n=5和n=6,ch-(LTQn)=n-1。对于n=4和任意的偶数n≥8,ch-(LTQn)=2。
(2)对于任意的整数n≥2,当使LTQn直径变大至少需要删除的边被删除时,我们找到了LTQn直径的增加值(用diam+(LT Qn)表示),diam+(LT Qn)=1。
(3)对于任意的整数n≥4,使LTQn直径减小,至少需要增加边的上界为2n-1。
High performance parallel computers are becoming more and more important in the ar-eas of scientific research, education, petroleum, meteorology and so on. In the parallel com-puting domain, it is an important research topic to study the connection pattern(interconnection network) of processors or process computer units in the parallel computer system. An inter-connection network can be represented by a simple graph G=(V, E), where V represents the vertex set and E represents the edge set. The topology properties of interconnection networks are important to the performance of parallel computers.
One of the critical performance factors of interconnection network is whether other existing networks can be embedded into this one. This can be modeled by the following graph embedding problem:given a host graph G2=(V2, E2) and a guest graph G1=(V1, E1), which represent the network where other networks are to be embedded and the network to be embedded, respectively. The problem becomes finding an injective mapping from each node of G1to a node of G2, and a mapping from each edge of G1to a path in G2. Two common measures of the embedding efficiency are dilation and expansion. A good interconnection network is supposed to possess ideal graph embedding ability as host graph, such that parallel algorithms in guest graphs can be migrated and executed on this network efficiently.
When the system scale becomes bigger, the faulty probability of the processors or links in the system becomes higher. When the fault occurs, we need to find the fault and repair it. The fault location is a more difficult problem. System-level fault diagnosis is to find the faulty processors or links. System-level fault diagnosis can improve the system reliability and usability without adding extra system input costs. System-level fault diagnosis can be divided into non-adaptive diagnosis and adaptive diagnosis by the test strategy. In adaptive diagnosis, the test allocations are dynamically decided by the previous test results, which can increase the efficiency of diagnosis compared to the non-adaptive diagnosis, and avoid the unnecessary tests.
The diameter of a graph is the maximum value of the shortest path length between any two nodes in graph. One of the critical performance factors of an interconnection network is the diameter, which determines the maximum communication time between any pair of nodes. By the definition of graph diameter, we know that deleting edges from a graph or adding edges to a graph may affect the distance between nodes, and then the diameter of the graph will be changed, where deleting edges can denote the scenario of edge faults. The change of graph diameter can affect its communication performance, thus, it is a meaningful topic to study the diameter variability arising from the deletion of edges or the addition of edges in a graph.
The hypercube network Qn has been proved to be one of the most popular interconnec-tion networks. The locally twisted cube is an important variant of hypercube. It has many attractive features as compared to the hypercube, for instance, the diameter is only about half of that of Qn. Let LT Qn denote the n-dimensional locally twisted cube.
This thesis will study the following properties of the locally twisted cube:mesh em-bedding property, tree embedding property, adaptive diagnosis problem and the diameter variability problem arising from the deletion of edges or the addition of edges. The major contributions are listed as follows.
1. The locally twisted cube is proved to have good mesh embedding property:
(1) For any integer n≥1, a2x2n-1mesh can be embedded in LTQn with dilation1and expansion1.
(2) For any integer n≥4, two node-disjoint4x2n-3meshes can be embedded in LTQn with dilation1and expansion2.
(3) For any integer n≥3, a4x (2n-2-1) mesh can be embedded in LTQn with dilation2.
The first two results are optimal in the sense that the dilations of all embeddings are1. The embedding of the2x2n-1mesh is also optimal in terms of expansion. We also present the analysis of2p x2q mesh embedding in locally twisted cubes.
2. The locally twisted cube is proved to have good tree embedding property:
(1) For any integer n≥2, we show that a complete binary tree with2n-1nodes can be embedded into LTQn with dilation2.
(2) For any integer n≥1, a binomial tree Bk(0≤k≤n) can be embedded into LTQn with any node as its root with dilation1.
3. Adaptive diagnosis in the locally twisted cube is studied in this thesis.
This thesis proves that for any integer n≥3, LTQn can be adaptively diagnosed using at most4parallel testing rounds, with at most n faulty nodes. The proof and algorithm description of adaptive diagnosis in LTQn also have been proposed.
4. Diameter variability problems arising from the deletion of edges and addition of edges in LTQn are investigated. Three results are obtained about diameter variability prob-lems:
(1) For any integer n≥2, we find the least number of edges (denoted by ch-(LT Qn)), whose deletion from LT Qn causes the diameter to increase. For n=2,n=3and any odd integer with n≥7, ch-(LTQn)=1. For any integer with n=5and n=6, ch-(LTQn)=n-1. For n=4and any even integer with n≥8, ch-(LTQn)=2.
(2) For any integer n≥2, we find the exact augmentation value of the diameter of LTQn, when edges(ch-(LTQn)) are deleted from LTQn(denoted by diam+(LTQn)), diam+(LTQn)=1.
(3) For any integer n≥4, the least number of edges whose addition to LTQn will decrease the diameter is at most2n-1.
引文
[1]B.Parhami. Algorithms and Architectures[M]. New York:Kluwer Academic Pub-lishers,2002.
[2]董强.几类规则互连网络的嵌入与容错嵌入研究[D].重庆大学,2010.
[3]陈国良等.并行计算机体系结构[M].北京：高等教育出版社,2002.
[4]陈国良.并行计算-结构·算法·编程(第3版)[M].北京：高等教育出版社,2011.
[5]S.-Y. Hsieh, G.-H. Chen and C.-W. Ho. Fault-free hamiltonian cycles in faulty ar-rangement graphs[J]. IEEE Transactions on Parallel and Distributed Systems,1999, 10(3):223-237.
[6]Q. Dong and X. Yang. Fault-tolerant embedding of meshes/tori in twisted cubes[J]. International Journal of Computer Mathematics,2011,88(8):1595-1602.
[7]P.-Y. Tsai. A note on an optimal result on fault-tolerant cycle-embedding in alternating group graphs[J]. Information Processing Letters,2011,111(8):375-378.
[8]J. Fan, X. Jia, X. Liu, S. Zhang and J. Yu. Efficient unicast in bijective connection networks with the restricted faulty node set[J]. Information Sciences,2011,181(11): 2303-2315.
[9]Y. Wang, J. Fan and Y. Han. Construction of independent spanning trees on twisted-cubes[C]. CSAE,2011:250-254.
[10]Y. Xiang and I. A. Stewart. Augmented k-ary n-cubes[J]. Information Sciences,2011, 181(1):239-256.
[11]X.-B. Chen. Paired many-to-many disjoint path covers of hypercubes with faulty edges[J]. Information Processing Letters,2012,112(3):61-66.
[12]Y. Wang, J. Fan, G. Zhou and X. Jia. Independent spanning trees on twisted cubes[J]. Journal of Parallel and Distributed Computing,2012,72(1):58-69.
[13]W.-S. Hong and S.-Y. Hsieh. Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model[J]. IEEE Transactions on Reliability,2012,61(1):140-148.
[14]P.-L. Lai. A systematic algorithm for identifying faults on hypercube-like networks Under the Comparison Model[J]. IEEE Transactions on Reliability,2012,61 (2):452-459.
[15]F. Harary. A survey of the theory of hypercube graphs[J]. Computers & Mathematics with Applications,1988,15(4):277-289.
[16]Y.-C. Tseng and T.-H. Lai. On the embedding of a class of regular graphs in a faulty hypercube[C]. ICPADS,1994:488-495.
[17]Y.-C. Tseng. Embedding a ring in a hypercube with both faulty links and faulty nodes[J]. Information Processing Letters,1996,59(4):217-222.
[18]Y.-C. Tseng and T.-H. Lai. On the embedding of a class of regular graphs in a faulty hypercube[J]. J. Parallel Distrib. Comput.,1996,37(2):200-206.
[19]S. L. Bezrukov. Embedding complete trees into the hypercube[J]. Discrete Applied Mathematics,2001,110(2-3):101-119.
[20]S.-Y. Hsieh. Embedding of cycles in the faulty hypercube[C]. Asia-Pacific Computer Systems Architecture Conference,2005:229-235.
[21]S.-Y. Hsieh and P.-Y. Yu. Cycle embedding on twisted cubes[C]. PDCAT,2006: 102-104.
[22]C.-H. Tsai and S.-Y. Jiang. Path bipancyclicity of hypercubes[J]. Information Pro-cessing Letters,2007,101(3):93-97.
[23]C.-H. Tsai and Y.-C. Lai. Conditional edge-fault-tolerant edge-bipancyclicity of hy-percubes[J]. Information Sciences,2007,177(24):5590-5597.
[24]S.-Y. Hsieh and Y.-F. Weng. Fault-tolerant embedding of pairwise independent hamil-tonian paths on a faulty hypercube with edge faults[J]. Theory of Computing Systems, 2009,45(2):407-425.
[25]X.-B. Chen. Edge-fault-tolerant diameter and bipanconnectivity of hypercubes[J]. Information Processing Letters,2010,110(24):1088-1092.
[26]M. Adler, E. Halperin, R. M. Karp and V. V. Vazirani. A stochastic process on the hypercube with applications to peer-to-peer networks[C]. STOC,2003:575-584.
[27]Ion Stoica, Robert Morris, David R. Karger, M. Frans Kaashoek and Hari Balakr-ishnan. Chord:A scalable peer-to-peer lookup service for internet applications[C]. SIGCOMM,2001:149-160.
[28]S. C. Rhea, B. Godfrey, B. Karp, J. Kubiatowicz, S. Ratnasamy, S. Shenker, I. Stoica and H. Yu. OpenDHT:a public DHT service and its uses[C]. SIGCOMM,2005: 73-84.
[29]I. Stoica, R. Morris, D. Liben-Nowell, D.R. Karger, M.F. Kaashoek, F. Dabek and H. Balakrishnan. Chord:a scalable peer-to-peer lookup protocol for Internet applica-tions[J]. IEEE/ACM Transactions on Networking, February 2003,11(1):17-32.
[30]M. Castro, P. Druschel, A.-M. Kermarrec and A.I.T. Rowstron. Scribe:A large-scale and decentralized application-level multicast infrastructure[J]. IEEE Journal on Selected Areas in Communications, October 2002,20(8):1489-1499.
[31]A.H. Mohajerzadeh, M.H. Yaghmaee, Z. Eskandari and H. Deldari. Energy efficient and congestion aware routing algorithms for Wireless Sensor Networks connected as Hypercube[C].IST,2008:324-329.
[32]H. Zhao and R. Liu. Hypercube-based key management in wireless sensor net-work[C]. WiCOM,2009:1-4.
[33]Z. Yang and J.J. Garcia-Luna-Aceves. Hop-reservation multiple access (HRMA) for ad-hoc networks[C]. INFOCOM,1999:194-201.
[34]S. C. Lee and Loyd R. Hook IV. Logic and computer design in nanospace[J]. IEEE Transactions on Computers,2008,57(7):965-977.
[35]J.Wu and Y. Wang. Hypercube-based multi-path social feature routing in human con-tact networks[J]. IEEE Transactions on Parallel and Distributed Systems,2012,99: 1-14.
[36]S. Abraham and K. Padmanabhan. The twisted cube topology for multiprocessors: a study in networks asymmetry [J]. Journal of Parallel and Distributed Computing, 1991,13(1):104-110.
[37]K. Efe. The crossed cube architecture for parallel computation[J]. IEEE Transactions on Parallel and Distributed Systems,1992,3(5):513-524.
[38]P. Cull and S. M. Larson. The mobius cubes[J]. IEEE Transactions on Computers, 1995,44(5):647-659.
[39]X. Yang, David J. Evans and Graham M. Megson. The locally twisted cubes[J]. In-ternational Journal of Computer Mathematics,2005,82(4):401-413.
[40]P. Kulasinghe and S. Bettayeb. Embedding binary trees into crossed cubes[J]. IEEE Transactions on Computers,1995,44(7):923-929.
[41]V. Auletta, A. A. Rescigno and V. Scarano. Embedding graphs onto the supercube[J]. IEEE Transactions on Computers,1995,44(4):593-597.
[42]X. Yang, Graham M. Megson and David J. Evans. Locally twisted cubes are 4-pancyclic[J]. Applied Mathematics Letters,2004,17(8):919-925.
[43]J. Fan, X. Lin and X. Jia. Optimal path embedding in crossed cubes [J]. IEEE Trans-actions on Parallel and Distributed Systems,2005,16(12):1190-1200.
[44]J. Fan, X. Jia and X. Lin. Optimal embeddings of paths with various lengths in twisted cubes[J]. IEEE Transactions on Parallel and Distributed Systems,2007,18(4):511-521.
[45]C.-J. Lai and C.-H. Tsai. Embedding a family of meshes into twisted cubes[J]. Infor-mation Processing Letters,2008,108(5):326-330.
[46]J. Fan and X. Jia. Edge-pancyclicity and path-embeddability of bijective connection graphs[J]. Information Sciences,2008,178(2):340-351.
[47]J.-M. Chang and J.-S. Yang. Fault-tolerant cycle-embedding in alternating group graphs[J]. Applied Mathematics and Computation,2008,197(2):760-767.
[48]Q. Dong, X. Yang and D. Wang. Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links [J]. Information Sciences,2010,180(1):198-208.
[49]H.-C. Chen, T.-L. Kung and L.-H. Hsu. Embedding a hamiltonian cycle in the crossed cube with two required vertices in the fixed positions[J]. Applied Mathematics and Computation,2011,217(24):10058-10065.
[50]T.-K. Li, C.-J. Lai and C.-H. Tsai. A novel algorithm to embed a multi-dimensional torus into a locally twisted cube[J], Theoretical Computer Science,2011,412(22): 2418-2424.
[51]Q. Dong, J. Zhou, Y. Fu and X. Yang. Embedding a mesh of trees in the crossed cube[J]. Information Processing Letters,2012,112(14-15):599-603.
[52]F. P. Preparata, G. Metze and R. T. Chien. On the connection assignment problem of diagnosable systems[J]. IEEE Transactions on Electronic Computers,1967, (6): 848-854.
[53]K.Nakajima. A new approach to system diagnosis[C]. Allerton,1981:679-706.
[54]樊建席.交叉立方体在两种策略下的可诊断性[J].计算机学报,1998,21(5)：456-462.
[55]A. Bjorklund. Optimal adaptive fault diagnosis of hypercubes[C]. SWAT,2000:527-534.
[56]J. Fan and X. Lin. The t/k-diagnosability of the BC graphs[J]. IEEE Transactions on Computers,2005,54(2):176-184.
[57]A. Okashita, T. Araki and Y. Shibata. Adaptive diagnosis of variant of the hyper-cube[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,2005, E88-A(3):728-735.
[58]X. Min, X. Hu and S. Shang. The conditional diagnosability of shuffle-cubes[J]. Jour-nal of Systems Science and Complexity,2010,23(1):81-90.
[59]邓伟,杨小帆,吴中福.面向系统级故障诊断的高效遗传算法[J].计算机学报,2007,7(30)：1115-1124.
[60]徐俊明.图论及其应用[M].合肥：中国科学技术大学出版社,2010.
[61]F. Harary. Graph Theory[M]. Massachusetts:Addison-Wesley,1969.
[62]R. Diestel. Graph Theory[M]. New York:Springer-Verlag,2005.
[63]喻昕,吴敏,王国军.一种新的交叉立方体最短路径路由算法[J].计算机学报,2007,30(3)：615-621.
[64]D.Wang. On embedding hamiltonian cycles in crossed cubes[J]. IEEE Transactions on Parallel and Distributed Systems,2008,19(3):334-346.
[65]P.-L. Lai and H.-C. Hsu. Constructing the nearly shortest path in crossed cubes[J]. Information Sciences,2009,179(14):2487-2493.
[66]C.-P. Chang and C.-C. Wu. Conditional fault diameter of crossed cubes[J]. Journal of Parallel and Distributed Computing,2009,69(1):91-99.
[67]S.-Y. Hsieh and C.-Y. Wu. Edge-fault-tolerant Hamiltonicity of locally twisted cubes under conditional edge faults[J]. Journal of Combinatorial Optimization,2010,19(1): 16-30.
[68]I.A. Stewart and Y. Xiang. Embedding long paths in k-ary n-cubes with faulty nodes and links[J]. IEEE Transactions on Parallel and Distributed Systems,2008,19(8): 1071-1085.
[69]Stewart I. A. and Y. Xiang. Bipanconnectivity and bipancyclicity in k-ary n-cubes[J], IEEE Transactions on Parallel and Distributed Systems,2009,20(1):25-33.
[70]徐俊明.组合网络理论[M].北京：科学出版社,2007.
[71]Y. Saad and M. H. Schultz. Topological properties of hypercubes[J]. IEEE Transac-tions on Computers,1988,37(7):867-872.
[72]X. Lin and L. M. Ni. Deadlock-free multicast wormhole routing in multicomputer networks[C]. ISCA,1991:116-125.
[73]P. K. McKinley X. Lin and L. M. Ni. Deadlock-free multicast wormhole routing in 2-D mesh multicomputers[J]. IEEE Transcactions on Parallel and Distributed Systems, 1994,5(8):793-804.
[74]D. Wang and L. Zhao. The twisted-cube connected networks[J]. Journal of Computer Science and Technology,1999,14(2):181-187.
[75]K. Efe. A variation on the hypercube with lower diameter[J]. IEEE Transactions on Computers,1991,40(11):1312-1316.
[76]P. Cull and S.M. Larson. On generalized twisted cubes[J]. Information Processing Letters,1995,55(1):53-55.
[77]J.-H. Park, H.-C. Kim and H.-S. Lim. Fault-Hamiltonicity of hypercube-like intercon-nection networks[C]. IPDPS,2005:1-10.
[78]常青彦,马美杰,徐俊明.局部扭立方体网络的容错泛圈性[J].中国科学技术大学学报,2006,36(6)：607-610,673.
[79]M. Ma and J.-M. Xu. Panconnectivity of locally twisted cubes[J]. Applied Mathe-matics Letters,2006,19(7):673-677.
[80]K.-S. Hu, S.-S. Yeoh and C.-Y. Node-pancyclicity and edgepancyclicity of hypercube variants[J]. Information Processing Letters,2007,102(1):1-7.
[81]S.Zhou. The conditional diagnosability of locally twisted cubes[C]. ICCSE,2009: 221-226.
[82]S.-Y. Hsieh and C.-J. Tu. Constructing edge-disjoint spanning trees in locally twisted cubes[J]. Theoretical Computer Science,2009,410(8-10):926-932.
[83]J.-C. Lin, J.-S. Yang,.-C. Hsu and J.-M. Chang. Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes[J]. Information Processing Letters, 2010,110(10):414-419.
[84]C.-J. Lai, J.-C. Chen and C.-H. Tsai. A systematic approach for embedding distinct Hamiltonian cycles with a prescribed edge in a locally twisted cube[C]. ICCET,2010: 105-109.
[85]R.-W. Hung. Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes[J]. Theoretical Computer Science,2011,412(35):4747-4753.
[86]X. Yang, L. Wang and L. Yang. Optimal broadcasting for locally twisted cubes[J]. Information Processing Letters,2012,112(4):129-134.
[87]Y. Liu, James K. Lan, Well Y. Chou and C. Chen. Constructing independent span-ning trees for locally twisted cubes[J]. Theoretical Computer Science,2011,412(22): 2237-2252.
[88]J. Fan and X. Jia. Embedding meshes into crossed cubes[J]. Information Sciences, 2007,177(15):3151-3160.
[89]C.-T. Ho and S. Lennart Johnsson. Embedding meshes in boolean cubes by graph decomposition[J]. Journal of Parallel and Distributed Computing,1990,8(4):325-339.
[90]C.-H. Tsai. Embedding of meshes in Mobius cubes[J]. Theoretical Computer Science, 2008,401(1-3):181-190.
[91]P.-J. Yang, S.-B. Tien and C. S. Raghavendra. Embedding of rings and meshes onto faulty hypercubes using free dimensions [J]. IEEE Transactions on Computers,1994, 43(5):608-613.
[92]J. Fan, X. Jia and X. Lin. Embedding of cycles in twisted cubes with edge-pancyclic[J]. Algorithmica,2008,51(3):264-282.
[93]M. M. Bae and B. Bose. Edge disjoint hamiltonian cycles in k-Ary n-Cubes and hypercubes[J]. IEEE Transactions on Computers,2003,52(10):1271-1284.
[94]X. Wang, J. Fan, X. Jia, S. Zhang and J. Yu. Embedding meshes into twisted-cubes[J]. Information Sciences,2011,181(14):3085-3099.
[95]J. Wu, Eduardo B. Fernandez and Y. Luo. Embedding of binomial trees in hypercubes with link faults[J]. Journal of Parallel and Distributed Computing,1998,54(1):59-74.
[96]樊建席,何力勤.BC互连网络及其性质[J].计算机学报,2003,26(1)：84-90.
[97]M.-C. Yang. Node-pancyclicity of faulty twisted cubes[C]. PDCAT,2009:63-66.
[98]阳惠.系统级故障诊断算法研究[D].重庆大学,2009.
[99]D. Wang. Diagnosability of hypercubes and enhanced hypercubes under the compari-son diagnosis model[J]. IEEE Transactions on Computers,1999,48(12):1369-1374.
[100]J. Fan. Diagnosability of the mobius cubes[J]. IEEE Transactions on Parallel and Distributed Systems,1998,9(9):923-928.
[101]J. Fan. Diagnosability of crossed cubes under the comparison diagnosis model[J]. IEEE Transactions on Parallel and Distributed Systems,2002,13(7):687-692.
[102]J. Fan and X. Lin. The t/k-diagnosability of the BC graphs[J]. IEEE Transactions on Computers,2005,54(2):176-184.
[103]G.-Y. Chang, G. J. Chang and G.-H. Chen. Diagnosabilities of regular networks[J]. IEEE Transactions on Parallel and Distributed Systems,2005,16(4):314-323.
[104]G.-Y. Chang. Conditional (t, k)-diagnosis under the PMC model[J]. IEEE Transac-tions on Parallel and Distributed Systems,2011,22(11):1797-1803.
[105]T.-K. Li, C.-H. Tsai and H.-C. Hsu. A fast fault-identification algorithm for bijective connection graphs using the PMC model[J]. Information Sciences,2012,187(1): 291-297.
[106]N.-W. Chang and S.-Y. Hsieh. Conditional diagnosability of augmented cubes under the PMC model[J]. IEEE Transactions on Dependable and Secure Computing,2012, 9(1):46-60.
[107]N.-W. Chang, T.-Y. Lin and S.-Y. Hsieh. Conditional diagnosability of k-Ary n-Cubes under the PMC model[J]. ACM Transactions on Design Automation of Electronic Systems,2012,17(4):46.
[108]C.-L. Kuo, M.-J. Yang, Y.-M. Chang and Y.-M. Yeh. High diagnosability of a se-quential diagnosis algorithm in hypercubes under the PMC model[J]. The Journal of Supercomputing,2012,61(3):1116-1134.
[109]M.-C. Yang. Conditional diagnosability of balanced hypercubes under the PMC model[J]. Information Sciences,2013,222:754-760.
[110]F. Barsi, F. Grandoni and P. Maestrini. A theory of diagnosability of digital systems[J]. IEEE Transactions on Computers,1976,25(6):585-593.
[111]K.-Y. Chwa and S. L. Hakimi. Schemes for fault-tolerant computing:A comparison of modularly redundant and t-diagnosable systems [J]. Information and Control,1981, 49(3):212-238.
[112]M. Malek. A comparison connection assignment for diagnosis of multiprocessor sys-tems[C]. ISCA,1980:31-36.
[113]J. Maeng and M. Malek. A comparison connection assignment for self-diagnosis of multiprocessor systems[C]. FTCS,1981:173-175.
[114]A. Sengupta and A. T. Dahbura. On self-diagnosable multiprocessor systems:diagno-sis by the comparison approach[J]. IEEE Transactions on Computers,1992,41(11): 1386-1396.
[115]H. Yang and X. Yang. A fast diagnosis algorithm for locally twisted cube multiproces-sor systems under the MM* model[J]. Computers & Mathematics with Applications, 2007,53(6):918-926.
[116]J.-C. Chen, C.-J. Lai and C.-H. Tsai. Optimal adaptive parallel diagnosis for a dis-tributed system modeled by dual-cubes[C]. FSKD,2011:1989-1993.
[117]J. R. Armstrong and F. G. Gray. Fault diagnosis in a boolean n cube array of micro-processors[J]. IEEE Transactions on Computers,1981,32(8):587-590.
[118]A.D.Friedman. A new measure of digital system diagnosis[C]. FTCS,1975:167-170.
[119]A. Kavianpour and K. H. Kim. Diagnosabilities of hypercubes under the pessimistic one-step diagnosis strategy[J]. IEEE Transactions on Computers,1991,40(2):232-237.
[120]A. K. Somani and O. Peleg. On diagnosability of large fault sets in regular topology-based computer systems[J]. IEEE Transactions on Computers,1996,45(8):892-903.
[121]A. T. Dahbura and G. M. Masson. An O(n2.5) fault identification algorithm for diag-nosable systems[J]. IEEE Transactions on Computers,1984,33(6):486-492.
[122]G. G. L. Meyer and G. M. Masson. An efficient fault diagnosis algorithm for sym-metric multiple processor architectures[J]. IEEE Transactions on Computers,1978, C-27(11):1059-1063.
[123]A. T. Dahbura, G. M. Masson and C.-L. Yang. Self-implicating structures for diag-nosable systems[J]. IEEE Transactions on Computers,1985,34(8):718-723.
[124]H. Yang, X. Yang and A. Nayak. A (4n-9)/3 diagnosis algorithm for generalized cube networks[J]. International Journal of Parallel, Emergent and Distributed Systems, 2010,25(3):171-182.
[125]H. Fujiwara and K. Kinoshita. On the computational complexity of system diagno-sis[J]. IEEE Transactions on Computers,1978, C-27(10):881-885.
[126]A. K. Somani, V. K. Agarwal and D. Avis. On the complexity of single fault set diagnosability and diagnosis problems[J]. IEEE Transactions on Computers,1989, 38(2):195-201.
[127]E. Kranakis and A. Pelc. Better adaptive diagnosis of hypercubes[J]. IEEE Transac-tions on Computers,2000,49(10):1013-1020.
[128]N. Graham and F. Harary. Changing and unchanging the diameter of a hypercube[J]. Discrete Applied Mathematics,1992,37/38:265-274.
[129]K. Day and A. E. Al-Ayyoub. Fault diameter of k-ary n-cube networks[J]. IEEE Transactions on Parallel and Distributed Systems,1997,8(9):903-907.
[130]I. Fris, I. Havel and P. Liebl. The diameter of the cube-connected cycles[J]. Informa-tion Processing Letters,1997,61(3):157-160.
[131]C.-P. Chang, T.-Y. Sung and L.-H. Hsu. Edge congestion and topological properties of crossed cubes[J]. IEEE Transactions on Parallel and Distributed Systems,2000, 11(1):64-80.
[132]J.-J.Wang, T.-Y. Ho, D. Ferrero and T.-Y. Sung. Diameter variability of cycles and tori[J]. Information Sciences,2008,178(14):2960-2967.
[133]T.-L. Kung, C.-K. Lin, T. Liang, L.-Y. Hsu and Jimmy J. M. Tan. Fault diameter of hypercubes with hybrid node and link faults[J]. Journal of Interconnection Networks, 2009,10(3):233-242.
[134]W. Zhou, J. Fan, X. Jia and S. Zhang. The spined cube:A new hypercube variant with smaller diameter[J]. Information Processing Letters,2011,111(12):561-567.
[135]T. Shi and M. Lu. fault-tolerant diameter for three family interconnection networks[J]. Journal of Combinatorial Optimization,2012,23(4):471-482.
[136]A. Bouabdallah, C. Delorme and S. Djelloul. Edge deletion preserving the diameter of the hypercube[J]. Discrete Applied Mathematics,1995,63(1):91-95.
[2]董强.几类规则互连网络的嵌入与容错嵌入研究[D].重庆大学,2010.
[3]陈国良等.并行计算机体系结构[M].北京：高等教育出版社,2002.
[4]陈国良.并行计算-结构·算法·编程(第3版)[M].北京：高等教育出版社,2011.
[5]S.-Y. Hsieh, G.-H. Chen and C.-W. Ho. Fault-free hamiltonian cycles in faulty ar-rangement graphs[J]. IEEE Transactions on Parallel and Distributed Systems,1999, 10(3):223-237.
[6]Q. Dong and X. Yang. Fault-tolerant embedding of meshes/tori in twisted cubes[J]. International Journal of Computer Mathematics,2011,88(8):1595-1602.
[7]P.-Y. Tsai. A note on an optimal result on fault-tolerant cycle-embedding in alternating group graphs[J]. Information Processing Letters,2011,111(8):375-378.
[8]J. Fan, X. Jia, X. Liu, S. Zhang and J. Yu. Efficient unicast in bijective connection networks with the restricted faulty node set[J]. Information Sciences,2011,181(11): 2303-2315.
[9]Y. Wang, J. Fan and Y. Han. Construction of independent spanning trees on twisted-cubes[C]. CSAE,2011:250-254.
[10]Y. Xiang and I. A. Stewart. Augmented k-ary n-cubes[J]. Information Sciences,2011, 181(1):239-256.
[11]X.-B. Chen. Paired many-to-many disjoint path covers of hypercubes with faulty edges[J]. Information Processing Letters,2012,112(3):61-66.
[12]Y. Wang, J. Fan, G. Zhou and X. Jia. Independent spanning trees on twisted cubes[J]. Journal of Parallel and Distributed Computing,2012,72(1):58-69.
[13]W.-S. Hong and S.-Y. Hsieh. Strong diagnosability and conditional diagnosability of augmented cubes under the comparison diagnosis model[J]. IEEE Transactions on Reliability,2012,61(1):140-148.
[14]P.-L. Lai. A systematic algorithm for identifying faults on hypercube-like networks Under the Comparison Model[J]. IEEE Transactions on Reliability,2012,61 (2):452-459.
[15]F. Harary. A survey of the theory of hypercube graphs[J]. Computers & Mathematics with Applications,1988,15(4):277-289.
[16]Y.-C. Tseng and T.-H. Lai. On the embedding of a class of regular graphs in a faulty hypercube[C]. ICPADS,1994:488-495.
[17]Y.-C. Tseng. Embedding a ring in a hypercube with both faulty links and faulty nodes[J]. Information Processing Letters,1996,59(4):217-222.
[18]Y.-C. Tseng and T.-H. Lai. On the embedding of a class of regular graphs in a faulty hypercube[J]. J. Parallel Distrib. Comput.,1996,37(2):200-206.
[19]S. L. Bezrukov. Embedding complete trees into the hypercube[J]. Discrete Applied Mathematics,2001,110(2-3):101-119.
[20]S.-Y. Hsieh. Embedding of cycles in the faulty hypercube[C]. Asia-Pacific Computer Systems Architecture Conference,2005:229-235.
[21]S.-Y. Hsieh and P.-Y. Yu. Cycle embedding on twisted cubes[C]. PDCAT,2006: 102-104.
[22]C.-H. Tsai and S.-Y. Jiang. Path bipancyclicity of hypercubes[J]. Information Pro-cessing Letters,2007,101(3):93-97.
[23]C.-H. Tsai and Y.-C. Lai. Conditional edge-fault-tolerant edge-bipancyclicity of hy-percubes[J]. Information Sciences,2007,177(24):5590-5597.
[24]S.-Y. Hsieh and Y.-F. Weng. Fault-tolerant embedding of pairwise independent hamil-tonian paths on a faulty hypercube with edge faults[J]. Theory of Computing Systems, 2009,45(2):407-425.
[25]X.-B. Chen. Edge-fault-tolerant diameter and bipanconnectivity of hypercubes[J]. Information Processing Letters,2010,110(24):1088-1092.
[26]M. Adler, E. Halperin, R. M. Karp and V. V. Vazirani. A stochastic process on the hypercube with applications to peer-to-peer networks[C]. STOC,2003:575-584.
[27]Ion Stoica, Robert Morris, David R. Karger, M. Frans Kaashoek and Hari Balakr-ishnan. Chord:A scalable peer-to-peer lookup service for internet applications[C]. SIGCOMM,2001:149-160.
[28]S. C. Rhea, B. Godfrey, B. Karp, J. Kubiatowicz, S. Ratnasamy, S. Shenker, I. Stoica and H. Yu. OpenDHT:a public DHT service and its uses[C]. SIGCOMM,2005: 73-84.
[29]I. Stoica, R. Morris, D. Liben-Nowell, D.R. Karger, M.F. Kaashoek, F. Dabek and H. Balakrishnan. Chord:a scalable peer-to-peer lookup protocol for Internet applica-tions[J]. IEEE/ACM Transactions on Networking, February 2003,11(1):17-32.
[30]M. Castro, P. Druschel, A.-M. Kermarrec and A.I.T. Rowstron. Scribe:A large-scale and decentralized application-level multicast infrastructure[J]. IEEE Journal on Selected Areas in Communications, October 2002,20(8):1489-1499.
[31]A.H. Mohajerzadeh, M.H. Yaghmaee, Z. Eskandari and H. Deldari. Energy efficient and congestion aware routing algorithms for Wireless Sensor Networks connected as Hypercube[C].IST,2008:324-329.
[32]H. Zhao and R. Liu. Hypercube-based key management in wireless sensor net-work[C]. WiCOM,2009:1-4.
[33]Z. Yang and J.J. Garcia-Luna-Aceves. Hop-reservation multiple access (HRMA) for ad-hoc networks[C]. INFOCOM,1999:194-201.
[34]S. C. Lee and Loyd R. Hook IV. Logic and computer design in nanospace[J]. IEEE Transactions on Computers,2008,57(7):965-977.
[35]J.Wu and Y. Wang. Hypercube-based multi-path social feature routing in human con-tact networks[J]. IEEE Transactions on Parallel and Distributed Systems,2012,99: 1-14.
[36]S. Abraham and K. Padmanabhan. The twisted cube topology for multiprocessors: a study in networks asymmetry [J]. Journal of Parallel and Distributed Computing, 1991,13(1):104-110.
[37]K. Efe. The crossed cube architecture for parallel computation[J]. IEEE Transactions on Parallel and Distributed Systems,1992,3(5):513-524.
[38]P. Cull and S. M. Larson. The mobius cubes[J]. IEEE Transactions on Computers, 1995,44(5):647-659.
[39]X. Yang, David J. Evans and Graham M. Megson. The locally twisted cubes[J]. In-ternational Journal of Computer Mathematics,2005,82(4):401-413.
[40]P. Kulasinghe and S. Bettayeb. Embedding binary trees into crossed cubes[J]. IEEE Transactions on Computers,1995,44(7):923-929.
[41]V. Auletta, A. A. Rescigno and V. Scarano. Embedding graphs onto the supercube[J]. IEEE Transactions on Computers,1995,44(4):593-597.
[42]X. Yang, Graham M. Megson and David J. Evans. Locally twisted cubes are 4-pancyclic[J]. Applied Mathematics Letters,2004,17(8):919-925.
[43]J. Fan, X. Lin and X. Jia. Optimal path embedding in crossed cubes [J]. IEEE Trans-actions on Parallel and Distributed Systems,2005,16(12):1190-1200.
[44]J. Fan, X. Jia and X. Lin. Optimal embeddings of paths with various lengths in twisted cubes[J]. IEEE Transactions on Parallel and Distributed Systems,2007,18(4):511-521.
[45]C.-J. Lai and C.-H. Tsai. Embedding a family of meshes into twisted cubes[J]. Infor-mation Processing Letters,2008,108(5):326-330.
[46]J. Fan and X. Jia. Edge-pancyclicity and path-embeddability of bijective connection graphs[J]. Information Sciences,2008,178(2):340-351.
[47]J.-M. Chang and J.-S. Yang. Fault-tolerant cycle-embedding in alternating group graphs[J]. Applied Mathematics and Computation,2008,197(2):760-767.
[48]Q. Dong, X. Yang and D. Wang. Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links [J]. Information Sciences,2010,180(1):198-208.
[49]H.-C. Chen, T.-L. Kung and L.-H. Hsu. Embedding a hamiltonian cycle in the crossed cube with two required vertices in the fixed positions[J]. Applied Mathematics and Computation,2011,217(24):10058-10065.
[50]T.-K. Li, C.-J. Lai and C.-H. Tsai. A novel algorithm to embed a multi-dimensional torus into a locally twisted cube[J], Theoretical Computer Science,2011,412(22): 2418-2424.
[51]Q. Dong, J. Zhou, Y. Fu and X. Yang. Embedding a mesh of trees in the crossed cube[J]. Information Processing Letters,2012,112(14-15):599-603.
[52]F. P. Preparata, G. Metze and R. T. Chien. On the connection assignment problem of diagnosable systems[J]. IEEE Transactions on Electronic Computers,1967, (6): 848-854.
[53]K.Nakajima. A new approach to system diagnosis[C]. Allerton,1981:679-706.
[54]樊建席.交叉立方体在两种策略下的可诊断性[J].计算机学报,1998,21(5)：456-462.
[55]A. Bjorklund. Optimal adaptive fault diagnosis of hypercubes[C]. SWAT,2000:527-534.
[56]J. Fan and X. Lin. The t/k-diagnosability of the BC graphs[J]. IEEE Transactions on Computers,2005,54(2):176-184.
[57]A. Okashita, T. Araki and Y. Shibata. Adaptive diagnosis of variant of the hyper-cube[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences,2005, E88-A(3):728-735.
[58]X. Min, X. Hu and S. Shang. The conditional diagnosability of shuffle-cubes[J]. Jour-nal of Systems Science and Complexity,2010,23(1):81-90.
[59]邓伟,杨小帆,吴中福.面向系统级故障诊断的高效遗传算法[J].计算机学报,2007,7(30)：1115-1124.
[60]徐俊明.图论及其应用[M].合肥：中国科学技术大学出版社,2010.
[61]F. Harary. Graph Theory[M]. Massachusetts:Addison-Wesley,1969.
[62]R. Diestel. Graph Theory[M]. New York:Springer-Verlag,2005.
[63]喻昕,吴敏,王国军.一种新的交叉立方体最短路径路由算法[J].计算机学报,2007,30(3)：615-621.
[64]D.Wang. On embedding hamiltonian cycles in crossed cubes[J]. IEEE Transactions on Parallel and Distributed Systems,2008,19(3):334-346.
[65]P.-L. Lai and H.-C. Hsu. Constructing the nearly shortest path in crossed cubes[J]. Information Sciences,2009,179(14):2487-2493.
[66]C.-P. Chang and C.-C. Wu. Conditional fault diameter of crossed cubes[J]. Journal of Parallel and Distributed Computing,2009,69(1):91-99.
[67]S.-Y. Hsieh and C.-Y. Wu. Edge-fault-tolerant Hamiltonicity of locally twisted cubes under conditional edge faults[J]. Journal of Combinatorial Optimization,2010,19(1): 16-30.
[68]I.A. Stewart and Y. Xiang. Embedding long paths in k-ary n-cubes with faulty nodes and links[J]. IEEE Transactions on Parallel and Distributed Systems,2008,19(8): 1071-1085.
[69]Stewart I. A. and Y. Xiang. Bipanconnectivity and bipancyclicity in k-ary n-cubes[J], IEEE Transactions on Parallel and Distributed Systems,2009,20(1):25-33.
[70]徐俊明.组合网络理论[M].北京：科学出版社,2007.
[71]Y. Saad and M. H. Schultz. Topological properties of hypercubes[J]. IEEE Transac-tions on Computers,1988,37(7):867-872.
[72]X. Lin and L. M. Ni. Deadlock-free multicast wormhole routing in multicomputer networks[C]. ISCA,1991:116-125.
[73]P. K. McKinley X. Lin and L. M. Ni. Deadlock-free multicast wormhole routing in 2-D mesh multicomputers[J]. IEEE Transcactions on Parallel and Distributed Systems, 1994,5(8):793-804.
[74]D. Wang and L. Zhao. The twisted-cube connected networks[J]. Journal of Computer Science and Technology,1999,14(2):181-187.
[75]K. Efe. A variation on the hypercube with lower diameter[J]. IEEE Transactions on Computers,1991,40(11):1312-1316.
[76]P. Cull and S.M. Larson. On generalized twisted cubes[J]. Information Processing Letters,1995,55(1):53-55.
[77]J.-H. Park, H.-C. Kim and H.-S. Lim. Fault-Hamiltonicity of hypercube-like intercon-nection networks[C]. IPDPS,2005:1-10.
[78]常青彦,马美杰,徐俊明.局部扭立方体网络的容错泛圈性[J].中国科学技术大学学报,2006,36(6)：607-610,673.
[79]M. Ma and J.-M. Xu. Panconnectivity of locally twisted cubes[J]. Applied Mathe-matics Letters,2006,19(7):673-677.
[80]K.-S. Hu, S.-S. Yeoh and C.-Y. Node-pancyclicity and edgepancyclicity of hypercube variants[J]. Information Processing Letters,2007,102(1):1-7.
[81]S.Zhou. The conditional diagnosability of locally twisted cubes[C]. ICCSE,2009: 221-226.
[82]S.-Y. Hsieh and C.-J. Tu. Constructing edge-disjoint spanning trees in locally twisted cubes[J]. Theoretical Computer Science,2009,410(8-10):926-932.
[83]J.-C. Lin, J.-S. Yang,.-C. Hsu and J.-M. Chang. Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes[J]. Information Processing Letters, 2010,110(10):414-419.
[84]C.-J. Lai, J.-C. Chen and C.-H. Tsai. A systematic approach for embedding distinct Hamiltonian cycles with a prescribed edge in a locally twisted cube[C]. ICCET,2010: 105-109.
[85]R.-W. Hung. Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes[J]. Theoretical Computer Science,2011,412(35):4747-4753.
[86]X. Yang, L. Wang and L. Yang. Optimal broadcasting for locally twisted cubes[J]. Information Processing Letters,2012,112(4):129-134.
[87]Y. Liu, James K. Lan, Well Y. Chou and C. Chen. Constructing independent span-ning trees for locally twisted cubes[J]. Theoretical Computer Science,2011,412(22): 2237-2252.
[88]J. Fan and X. Jia. Embedding meshes into crossed cubes[J]. Information Sciences, 2007,177(15):3151-3160.
[89]C.-T. Ho and S. Lennart Johnsson. Embedding meshes in boolean cubes by graph decomposition[J]. Journal of Parallel and Distributed Computing,1990,8(4):325-339.
[90]C.-H. Tsai. Embedding of meshes in Mobius cubes[J]. Theoretical Computer Science, 2008,401(1-3):181-190.
[91]P.-J. Yang, S.-B. Tien and C. S. Raghavendra. Embedding of rings and meshes onto faulty hypercubes using free dimensions [J]. IEEE Transactions on Computers,1994, 43(5):608-613.
[92]J. Fan, X. Jia and X. Lin. Embedding of cycles in twisted cubes with edge-pancyclic[J]. Algorithmica,2008,51(3):264-282.
[93]M. M. Bae and B. Bose. Edge disjoint hamiltonian cycles in k-Ary n-Cubes and hypercubes[J]. IEEE Transactions on Computers,2003,52(10):1271-1284.
[94]X. Wang, J. Fan, X. Jia, S. Zhang and J. Yu. Embedding meshes into twisted-cubes[J]. Information Sciences,2011,181(14):3085-3099.
[95]J. Wu, Eduardo B. Fernandez and Y. Luo. Embedding of binomial trees in hypercubes with link faults[J]. Journal of Parallel and Distributed Computing,1998,54(1):59-74.
[96]樊建席,何力勤.BC互连网络及其性质[J].计算机学报,2003,26(1)：84-90.
[97]M.-C. Yang. Node-pancyclicity of faulty twisted cubes[C]. PDCAT,2009:63-66.
[98]阳惠.系统级故障诊断算法研究[D].重庆大学,2009.
[99]D. Wang. Diagnosability of hypercubes and enhanced hypercubes under the compari-son diagnosis model[J]. IEEE Transactions on Computers,1999,48(12):1369-1374.
[100]J. Fan. Diagnosability of the mobius cubes[J]. IEEE Transactions on Parallel and Distributed Systems,1998,9(9):923-928.
[101]J. Fan. Diagnosability of crossed cubes under the comparison diagnosis model[J]. IEEE Transactions on Parallel and Distributed Systems,2002,13(7):687-692.
[102]J. Fan and X. Lin. The t/k-diagnosability of the BC graphs[J]. IEEE Transactions on Computers,2005,54(2):176-184.
[103]G.-Y. Chang, G. J. Chang and G.-H. Chen. Diagnosabilities of regular networks[J]. IEEE Transactions on Parallel and Distributed Systems,2005,16(4):314-323.
[104]G.-Y. Chang. Conditional (t, k)-diagnosis under the PMC model[J]. IEEE Transac-tions on Parallel and Distributed Systems,2011,22(11):1797-1803.
[105]T.-K. Li, C.-H. Tsai and H.-C. Hsu. A fast fault-identification algorithm for bijective connection graphs using the PMC model[J]. Information Sciences,2012,187(1): 291-297.
[106]N.-W. Chang and S.-Y. Hsieh. Conditional diagnosability of augmented cubes under the PMC model[J]. IEEE Transactions on Dependable and Secure Computing,2012, 9(1):46-60.
[107]N.-W. Chang, T.-Y. Lin and S.-Y. Hsieh. Conditional diagnosability of k-Ary n-Cubes under the PMC model[J]. ACM Transactions on Design Automation of Electronic Systems,2012,17(4):46.
[108]C.-L. Kuo, M.-J. Yang, Y.-M. Chang and Y.-M. Yeh. High diagnosability of a se-quential diagnosis algorithm in hypercubes under the PMC model[J]. The Journal of Supercomputing,2012,61(3):1116-1134.
[109]M.-C. Yang. Conditional diagnosability of balanced hypercubes under the PMC model[J]. Information Sciences,2013,222:754-760.
[110]F. Barsi, F. Grandoni and P. Maestrini. A theory of diagnosability of digital systems[J]. IEEE Transactions on Computers,1976,25(6):585-593.
[111]K.-Y. Chwa and S. L. Hakimi. Schemes for fault-tolerant computing:A comparison of modularly redundant and t-diagnosable systems [J]. Information and Control,1981, 49(3):212-238.
[112]M. Malek. A comparison connection assignment for diagnosis of multiprocessor sys-tems[C]. ISCA,1980:31-36.
[113]J. Maeng and M. Malek. A comparison connection assignment for self-diagnosis of multiprocessor systems[C]. FTCS,1981:173-175.
[114]A. Sengupta and A. T. Dahbura. On self-diagnosable multiprocessor systems:diagno-sis by the comparison approach[J]. IEEE Transactions on Computers,1992,41(11): 1386-1396.
[115]H. Yang and X. Yang. A fast diagnosis algorithm for locally twisted cube multiproces-sor systems under the MM* model[J]. Computers & Mathematics with Applications, 2007,53(6):918-926.
[116]J.-C. Chen, C.-J. Lai and C.-H. Tsai. Optimal adaptive parallel diagnosis for a dis-tributed system modeled by dual-cubes[C]. FSKD,2011:1989-1993.
[117]J. R. Armstrong and F. G. Gray. Fault diagnosis in a boolean n cube array of micro-processors[J]. IEEE Transactions on Computers,1981,32(8):587-590.
[118]A.D.Friedman. A new measure of digital system diagnosis[C]. FTCS,1975:167-170.
[119]A. Kavianpour and K. H. Kim. Diagnosabilities of hypercubes under the pessimistic one-step diagnosis strategy[J]. IEEE Transactions on Computers,1991,40(2):232-237.
[120]A. K. Somani and O. Peleg. On diagnosability of large fault sets in regular topology-based computer systems[J]. IEEE Transactions on Computers,1996,45(8):892-903.
[121]A. T. Dahbura and G. M. Masson. An O(n2.5) fault identification algorithm for diag-nosable systems[J]. IEEE Transactions on Computers,1984,33(6):486-492.
[122]G. G. L. Meyer and G. M. Masson. An efficient fault diagnosis algorithm for sym-metric multiple processor architectures[J]. IEEE Transactions on Computers,1978, C-27(11):1059-1063.
[123]A. T. Dahbura, G. M. Masson and C.-L. Yang. Self-implicating structures for diag-nosable systems[J]. IEEE Transactions on Computers,1985,34(8):718-723.
[124]H. Yang, X. Yang and A. Nayak. A (4n-9)/3 diagnosis algorithm for generalized cube networks[J]. International Journal of Parallel, Emergent and Distributed Systems, 2010,25(3):171-182.
[125]H. Fujiwara and K. Kinoshita. On the computational complexity of system diagno-sis[J]. IEEE Transactions on Computers,1978, C-27(10):881-885.
[126]A. K. Somani, V. K. Agarwal and D. Avis. On the complexity of single fault set diagnosability and diagnosis problems[J]. IEEE Transactions on Computers,1989, 38(2):195-201.
[127]E. Kranakis and A. Pelc. Better adaptive diagnosis of hypercubes[J]. IEEE Transac-tions on Computers,2000,49(10):1013-1020.
[128]N. Graham and F. Harary. Changing and unchanging the diameter of a hypercube[J]. Discrete Applied Mathematics,1992,37/38:265-274.
[129]K. Day and A. E. Al-Ayyoub. Fault diameter of k-ary n-cube networks[J]. IEEE Transactions on Parallel and Distributed Systems,1997,8(9):903-907.
[130]I. Fris, I. Havel and P. Liebl. The diameter of the cube-connected cycles[J]. Informa-tion Processing Letters,1997,61(3):157-160.
[131]C.-P. Chang, T.-Y. Sung and L.-H. Hsu. Edge congestion and topological properties of crossed cubes[J]. IEEE Transactions on Parallel and Distributed Systems,2000, 11(1):64-80.
[132]J.-J.Wang, T.-Y. Ho, D. Ferrero and T.-Y. Sung. Diameter variability of cycles and tori[J]. Information Sciences,2008,178(14):2960-2967.
[133]T.-L. Kung, C.-K. Lin, T. Liang, L.-Y. Hsu and Jimmy J. M. Tan. Fault diameter of hypercubes with hybrid node and link faults[J]. Journal of Interconnection Networks, 2009,10(3):233-242.
[134]W. Zhou, J. Fan, X. Jia and S. Zhang. The spined cube:A new hypercube variant with smaller diameter[J]. Information Processing Letters,2011,111(12):561-567.
[135]T. Shi and M. Lu. fault-tolerant diameter for three family interconnection networks[J]. Journal of Combinatorial Optimization,2012,23(4):471-482.
[136]A. Bouabdallah, C. Delorme and S. Djelloul. Edge deletion preserving the diameter of the hypercube[J]. Discrete Applied Mathematics,1995,63(1):91-95.