Abstract
The crossed cube is a prominent variant of the well known, highly regular-structured hypercube. In [24], it is shown that due to the loss of regularity in link topology, generating Hamiltonian cycles, even in a healthy crossed cube, is a more complicated procedure than in the hypercube, and fewer Hamiltonian cycles can be generated in the crossed cube. Because of the importance of fault-tolerance in interconnection networks, in this paper, we treat the problem of embedding Hamiltonian cycles into a crossed cube with failed links. We establish a relationship between the faulty link distribution and the crossed cube's tolerability. A succinct algorithm is proposed to find a Hamiltonian cycle in a CQ n tolerating up to n-2 failed links.
Original language | English |
---|---|
Article number | 6133282 |
Pages (from-to) | 2117-2124 |
Number of pages | 8 |
Journal | IEEE Transactions on Parallel and Distributed Systems |
Volume | 23 |
Issue number | 11 |
DOIs | |
State | Published - 2012 |
Keywords
- Crossed cube
- Hamiltonian cycle
- embedding
- fault tolerance
- faulty links
- interconnection networks