We study the embedding of Hamiltonian cycle in the Crossed Cube, a prominent variant of the classical hypercube, which is obtained by crossing some straight links of a hypercube, and has been attracting much research interest in literatures since its proposal. We will show that due to the loss of link-topology regularity, generating Hamiltonian cycles in a crossed cube is a more complicated procedure than in its original counterpart. The paper studies how the crossed links affect an otherwise succinct process to generate a host of well-structured Hamiltonian cycles traversing all nodes. The condition for generating these Hamiltonian cycles in a crossed cube is proposed. An algorithm is presented that works out a Hamiltonian cycle for a given link permutation. The useful properties revealed and algorithm proposed in this paper can find their way when system designers evaluate a candidate network' s competence and suitability, balancing regularity and other performance criteria, in choosing an interconnection network.
|Number of pages||13|
|Journal||IEEE Transactions on Parallel and Distributed Systems|
|State||Published - 1 Mar 2008|
- Crossed cube
- Hamiltonian cycles
- Interconnection architectures
- Network topology