Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20]

@

Journal of Information Science and Engineering, Vol. 25 No. 2, pp. 531-542 (March 2009)

Hamiltonicity of the Pyramid Network with or without Fault*

Ruei-Yu Wu1 and Dyi-Rong Duh2
1Department of Management Information Systems
Hwa Hsia Institute of Technology
Taipei Hsien, 235 Taiwan
2Department of Computer Science and Information Engineering
National Chi Nan University
Nantou Hsien, 545 Taiwan

Sarbazi-Azad, Ould-Khaoua, and Mackenzie proved in 2001 that there exists a Hamiltonian cycle in a pyramid network and they also constructed a Hamiltonian path between apex and each of 4 frontiers of a pyramid network. The fault tolerance is a crucial matter for parallel computing, especially in a large network. This work improves Sarbazi-Azad et al.s result and considers other relative problems in pyramid networks such as the fault tolerant Hamiltonian problem and the Hamiltonian-connected problem. The problem of finding Hamiltonian cycles in a pyramid network with one faulty node (link) is investigated. Additionally, the Hamiltonian-connectedness of a pyramid network can be shown by constructing a Hamiltonian path between any two distinct nodes in it.

Keywords: pyramid networks, Hamiltonian cycle, Hamiltonian-connectedness, fault tolerance, interconnection networks

Full Text () Retrieve PDF document (200903_12.pdf)

Received May 14, 2007; revised September 19, 2007 & March 18, 2008; accepted April 17, 2008.
Communicated by Tsan-sheng Hsu.
* This work was also partially supported by the National Science Council of Taiwan, R.O.C. under contract No. NSC 91-2213-E-260-003-.