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

fYear

2002

fDate

6/24/1905 12:00:00 AM

Firstpage

157

Lastpage

162

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel Architectures, Algorithms and Networks, 2002. I-SPAN '02. Proceedings. International Symposium on

Conference_Location

Makati City, Metro Manila

ISSN

1087-4089

Print_ISBN

0-7695-1579-7

Type

conf

DOI

10.1109/ISPAN.2002.1004279

Filename

1004279

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1631339