Title :
Embedding Hamiltonian paths and Hamiltonian cycles in faulty pancake graphs
Author :
Hung, Chun-Nan ; Liang, Kao-Yung ; Hsu, Lih-Hsing
Author_Institution :
Dept. of Comput. Sci. & Inf. Eng., Da-Yet Univ., Changhua, Taiwan
fDate :
6/24/1905 12:00:00 AM
Abstract :
The use of pancake and star networks as an interconnection network has been studied by many researchers. The fault tolerance for Hamiltonian networks is also an important issue. In this paper, we prove that an n-dimensional faulty pancake graph contains a Hamiltonian cycle with |F| ⩽ n - 3 faults. Furthermore, there exist Hamiltonian paths between two arbitrary but distinct nodes in a faulty pancake graph with |F| ⩽ n - 4 faults
Keywords :
fault tolerant computing; multiprocessor interconnection networks; Hamiltonian cycles; Hamiltonian networks; Hamiltonian paths embedding; fault tolerance; faulty pancake graph; interconnection network; pancake networks; star networks; Computer science; Contracts; Councils; Fault tolerance; Fault tolerant systems; Hypercubes; Information science; Iron; Multiprocessor interconnection networks; Terminology;
Conference_Titel :
Parallel Architectures, Algorithms and Networks, 2002. I-SPAN '02. Proceedings. International Symposium on
Conference_Location :
Makati City, Metro Manila
Print_ISBN :
0-7695-1579-7
DOI :
10.1109/ISPAN.2002.1004279
