A Systematic Algorithm for Embedding Hamiltonian Cycle in Hierarchical Crossed Cubes

The hypercube has been widely used as the interconnection network in parallel computers. The crossed cube is an variation of hypercube and preserves many of its desirable properties. The hierarchical crossed cube draws upon constructions used within the hypercube and also the crossed cube. The hierarchical crossed cube is suitable for massively parallel systems with thousands of processors and owns many alluring features, such as symmetry and logarithmic diameter. In this paper, we adopt the concept of Hamiltonian cycle pattern and provide a systematic and linear algorithm to generate a Hamiltonian cycle of the hierarchical crossed cube. Furthermore, we obtain a lower bound for the number of Hamiltonian cycles in a hierarchical crossed cube.