Fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges
Fault-free mutually independent Hamiltonian cycles in hypercubes with faulty edges
复制标题
DOI：
10.1007/s10878-006-9018-4
复制
发表时间：
2006-10
影响因子：
1
通讯作者：
S. Hsieh;Pei-Yu Yu-Pei-Yu-Yu-2114104759
中科院分区：
文献类型：
--
作者：
S. Hsieh;Pei-Yu Yu-Pei-Yu-Yu-2114104759
如果两条Hamilton路的第i个顶点在1和n之间是不同的，则称这两条路是完全独立的，其中n是给定图的顶点数。如果集合中的两条任意哈密尔顿路是完全独立的，则称集合中的哈密尔顿路是互完全独立的。另一方面，如果两个Hamilton圈都从一个公共点v开始，并且两个圈的第i个顶点不同，则两个Hamilton圈是独立的。如果集合中任意两个不同的圈从atv开始相互独立，则称集合中的哈密尔顿圈从atv开始相互独立。三维超立方体被广泛地用作并行机的体系结构。本文研究了n维超立方体的容错性，证明了n维n相对于最坏的情况，可容忍的故障边缘的数量是最佳的。
Two Hamiltonian paths are said to befully independentif theith vertices of both paths are distinct for allibetween 1 andn, wherenis the number of vertices of the given graph. Hamiltonian paths in a set are said to bemutually fully independentif two arbitrary Hamiltonian paths in the set are fully independent. On the other hand, two Hamiltonian cycles areindependent starting atvif both cycles start at a common vertexvand theith vertices of both cycles are distinct for allibetween 2 andn. Hamiltonian cycles in a set are said to bemutually independent starting atvif any two different cycles in the set are independent starting atv. Then-dimensional hypercube is widely used as the architecture for parallel machines. In this paper, we study its fault-tolerant property and show that ann-dimensional hypercube with at mostn−2 faulty edges can embed a set of fault-free mutually fully independent Hamiltonian paths between two adjacent vertices, and can embed a set of fault-free mutually independent Hamiltonian cycles starting at a given vertex. The number of tolerable faulty edges is optimal with respect to a worst case.