On Embedding Hamiltonian Cycles in Crossed Cubes
Dajin Wang · IEEE Transactions on Parallel and Distributed Systems · 2008
We study the embedding of Hamiltonian cycle in the Crossed Cube, which is a prominent variant of the classical hypercube, 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 the 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.