HAMILTONIAN CYCLE EMBEDDING FOR FAULT TOLERANCE IN DUAL-CUBE
Yamin Li, Shietung Peng, Wanming Chu · 2002
The hypercube has been widely used as the interconnection network (IN) in parallel computers. However, the major drawback of the hypercube is the increase in the number of communication links for each node with the increase in the total number of nodes in the system. A dual-cube DC(m) has m + 1 links per node where m is the degree of a cluster (m-cube), one more link is used for connecting to a node in another cluster. The dualcube mitigates the problem of increasing number of links in the large-scale hypercube network while keeps most of the topological properties of the hypercube network. Embedding a linear array or a ring into interconnection networks even when faulty-links exit is an important issue for the design of INs. In this paper, we show that a hamiltonian cycle exists in a DC(m) with up to m − 1 faulty links. This is optimal because the degree of a DC(m) is m + 1. We also give efficient algorithms for constructing hamiltonian cycles in DC(m). KEY WORDS Interconnection networks, hypercube, hamiltonian cycle, Gray code, fault-tolerant embedding 1.