Hamiltonian Cycles and Hamiltonian Paths in Faulty Burnt Pancake Graphs
Hamiltonian Cycles and Hamiltonian Paths in Faulty Burnt Pancake Graphs
复制标题
DOI：
10.1093/ietisy/e90-d.4.716
复制
发表时间：
2007-03
期刊：
影响因子：
--
通讯作者：
K. Kaneko
中科院分区：
文献类型：
--
作者：
K. Kaneko
近年来，并行处理系统的研究非常活跃，提出了许多复杂的拓扑结构。烧焦的煎饼图就是这样一种拓扑结构。本文证明了n次故障烧饼图，当故障元素个数小于等于n-2时，具有无故障哈密顿循环；当故障元素个数小于等于n- 3时，在任意一对非故障节点之间具有无故障哈密顿路径。
Recently, research on parallel processing systems is very active, and many complex topologies have been proposed. A burnt pancake graph is one such topology. In this paper, we prove that a faulty burnt pancake graph with degree n has a fault-free Hamiltonian cycle if the number of the faulty elements is n-2 or less, and it has a fault-free Hamiltonian path between any pair of nonfaulty nodes if the number of the faulty elements is n - 3 or less.