Fault-free longest paths in star networks with conditional link faults
Resource
Theoretical Computer Science 410 (8-10): 766-775
Journal
Theoretical Computer Science
Pages
766-775
Date Issued
2009
Date
2009
Author(s)
Abstract
The star network, which belongs to the class of Cayley graphs, is one of the most versatile interconnection networks for parallel and distributed computing. In this paper, adopting the conditional fault model in which each node is assumed to be incident with two or more fault-free links, we show that an n-dimensional star network can tolerate up to 2 n - 7 link faults, and be strongly (fault-free) Hamiltonian laceable, where n ≥ 4. In other words, we can embed a fault-free linear array of length n ! - 1 (n ! - 2) in an n-dimensional star network with up to 2 n - 7 link faults, if the two end nodes belong to different partite sets (the same partite set). The result is optimal with respect to the number of link faults tolerated. It is already known that under the random fault model, an n-dimensional star network can tolerate up to n - 3 faulty links and be strongly Hamiltonian laceable, for n ≥ 3. © 2008 Elsevier B.V. All rights reserved.
Subjects
Conditional fault model; Embedding; Fault tolerance; Hamiltonian laceability; Random fault model; Star network
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
51.pdf
Size
1.3 MB
Format
Adobe PDF
Checksum
(MD5):a2a64efc84921975bbaf7a377d0224e1