Embedding a fault-free hamiltonian cycle in a class of faulty generalized honeycomb tori

作者：Dong Qiang^*; Yang Xiaofan; Zhao Juan

来源：Computers & Electrical Engineering, 2009, 35(6): 942-950.

DOI：10.1016/j.compeleceng.2008.09.005

• Interconnection network
• Generalized honeycomb torus
• Hamiltonian cycle
• Fault-tolerance
• Parallel computing

Generalized honeycomb torus (GHT) is recognized as an attractive alternative to existing torus interconnection networks in parallel computing systems. Assume that m and d are integers with m >= 2 and d >= 8. This paper addresses the fault-tolerant hamiltonicity of GHT(m, 2d, d) with fault set F = {(w, y), (x, y)}, where w < x, w + y is even and x + y is odd. We show that such a faulty GHT is hamiltonian by presenting a systematic method for constructing a fault-free hamiltonian cycle. This result reveals another appealing feature of GHTs.

• 出版日期2009-11
• 单位南宁师范大学; 重庆大学