A Systematic Approach for Finding Hamiltonian Cycles with a Prescribed Edge in Crossed Cubes
The crossed cube is one of the most notable variations of hypercube, but some properties of the former are superior to those of the latter. For example, the diameter of the crossed cube is almost the half of that of the hypercube. In this paper, we focus on the problem embedding a Hamiltonian cycle through an arbitrary given edge in the crossed cube. We give necessary and sufficient condition for determining whether a given permutation with n elements over Zn generates a Hamiltonian cycle pattern of the crossed cube. Moreover, we obtain a lower bound for the number of different Hamiltonian cycles passing through a given edge in an n-dimensional crossed cube. Our work extends some recently obtained results.
[1] E. Abuelrub and S. Bettayeb, "Embedding Rings into Faulty Twisted
Hypercubes," Computers and Artificial Intelligence, vol. 16, pp. 425-441,
1997.
[2] S. G. Akl,, Parallel Computation: Models and Methods, Upper Saddle
River, NJ: Prentice-Hall, 1997.
[3] K. Efe,"The Crossed Cube Architecture for Parallel Computing," IEEE
Trans. Parallel and Distributed Systems, vol. 3, no. 5, pp. 513-524, 1992.
[4] K. Efe, P. K. Blackwell, W. Slough, and T. Shiau, "Topological Properties
of the Crossed Cube Architecture," Parallel Computing, vol. 20, pp. 1763-
1775, 1994.
[5] J. Fan, X. Lin, and X. Jia, "Node-pancyclicity and edge-pancyclicity of
Crossed cubes," Information Processing Letters, vol. 93, pp. 133-138,
2005.
[6] J. P. Hayes and T. N. Mudge, "Hypercube supercomputer," Proc. IEEE,
vol. 17, pp. 1829-1841, 1989.
[7] W. T. Huang, Y. C. Chuang, J. M. Tan, and L. H. Hsu, "On the
Fault-Tolerant Hamiltonicity of Faulty Crossed Cubes," IEICE Trans.
Fundamentals, vol. E85-A, no. 6, pp. 1359-1370, 2002.
[8] H. S. Hung, J. S. Fu, and G. H. Chen, "Fault-free Hamiltonian cycles
in Crossed Cubes with Conditional Link Faults," Information Sciences,
vol. 177, pp. 5664-5674, 2007.
[9] F. T. Leighton, Introduction to Parallel Algorithms and Architectures:
arrays, trees, hypercubes. San Mateo: Morgan Kaufman, 1992.
[10] SGI, Origin2000 Rackmount Ower-s Guide, 007-3456-003,
http://techpubs.sgi.com/, 1997.
[11] L. W. Tucker and G. G. Robertson, "Architecture and applications of
the connection machine," IEEE Computer, vol. 21, pp. 26-38, 1988.
[12] D. Wang,"On Embedding Hamiltonian Cycles in Crossed Cubes," IEEE
Trans. Parallel and Distributed Systems, vol. 19, no. 3, pp. 334-346, 2008.
[13] M. C. Yang, T. K. Li, J. M. Tan, and L. H. Hsu, "Fault-tolerant Cycleembedding
of Crossed Cubes," Information Processing Letters, vol. 88,
pp. 149-154, 2003.
[14] S. Q. Zheng and S. Latifi, "Optimal Simulation of Linear Multiprocessor
Architectures on Multiply-Twisted Cube Using Generalized Gray Code,"
IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 6, pp. 612-619,
1996.
[1] E. Abuelrub and S. Bettayeb, "Embedding Rings into Faulty Twisted
Hypercubes," Computers and Artificial Intelligence, vol. 16, pp. 425-441,
1997.
[2] S. G. Akl,, Parallel Computation: Models and Methods, Upper Saddle
River, NJ: Prentice-Hall, 1997.
[3] K. Efe,"The Crossed Cube Architecture for Parallel Computing," IEEE
Trans. Parallel and Distributed Systems, vol. 3, no. 5, pp. 513-524, 1992.
[4] K. Efe, P. K. Blackwell, W. Slough, and T. Shiau, "Topological Properties
of the Crossed Cube Architecture," Parallel Computing, vol. 20, pp. 1763-
1775, 1994.
[5] J. Fan, X. Lin, and X. Jia, "Node-pancyclicity and edge-pancyclicity of
Crossed cubes," Information Processing Letters, vol. 93, pp. 133-138,
2005.
[6] J. P. Hayes and T. N. Mudge, "Hypercube supercomputer," Proc. IEEE,
vol. 17, pp. 1829-1841, 1989.
[7] W. T. Huang, Y. C. Chuang, J. M. Tan, and L. H. Hsu, "On the
Fault-Tolerant Hamiltonicity of Faulty Crossed Cubes," IEICE Trans.
Fundamentals, vol. E85-A, no. 6, pp. 1359-1370, 2002.
[8] H. S. Hung, J. S. Fu, and G. H. Chen, "Fault-free Hamiltonian cycles
in Crossed Cubes with Conditional Link Faults," Information Sciences,
vol. 177, pp. 5664-5674, 2007.
[9] F. T. Leighton, Introduction to Parallel Algorithms and Architectures:
arrays, trees, hypercubes. San Mateo: Morgan Kaufman, 1992.
[10] SGI, Origin2000 Rackmount Ower-s Guide, 007-3456-003,
http://techpubs.sgi.com/, 1997.
[11] L. W. Tucker and G. G. Robertson, "Architecture and applications of
the connection machine," IEEE Computer, vol. 21, pp. 26-38, 1988.
[12] D. Wang,"On Embedding Hamiltonian Cycles in Crossed Cubes," IEEE
Trans. Parallel and Distributed Systems, vol. 19, no. 3, pp. 334-346, 2008.
[13] M. C. Yang, T. K. Li, J. M. Tan, and L. H. Hsu, "Fault-tolerant Cycleembedding
of Crossed Cubes," Information Processing Letters, vol. 88,
pp. 149-154, 2003.
[14] S. Q. Zheng and S. Latifi, "Optimal Simulation of Linear Multiprocessor
Architectures on Multiply-Twisted Cube Using Generalized Gray Code,"
IEEE Trans. Parallel and Distributed Systems, vol. 7, no. 6, pp. 612-619,
1996.
@article{"International Journal of Information, Control and Computer Sciences:52617", author = "Jheng-Cheng Chen and Chia-Jui Lai and Chang-Hsiung Tsai and ", title = "A Systematic Approach for Finding Hamiltonian Cycles with a Prescribed Edge in Crossed Cubes", abstract = "The crossed cube is one of the most notable variations of hypercube, but some properties of the former are superior to those of the latter. For example, the diameter of the crossed cube is almost the half of that of the hypercube. In this paper, we focus on the problem embedding a Hamiltonian cycle through an arbitrary given edge in the crossed cube. We give necessary and sufficient condition for determining whether a given permutation with n elements over Zn generates a Hamiltonian cycle pattern of the crossed cube. Moreover, we obtain a lower bound for the number of different Hamiltonian cycles passing through a given edge in an n-dimensional crossed cube. Our work extends some recently obtained results.
", keywords = "Interconnection network, Hamiltonian, crossed cubes, prescribed edge.", volume = "4", number = "4", pages = "679-5", }
