Journal
THEORETICAL COMPUTER SCIENCE
Volume 410, Issue 8-10, Pages 766-775Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2008.11.012
Keywords
Conditional fault model; Embedding; Fault tolerance; Hamiltonian laceability; Random fault model; Star network
Categories
Funding
- National Science Council of the Republic of China, Taiwan [95-2221-E-239-002]
Ask authors/readers for more resources
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 2n - 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 2n - 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. (C) 2008 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available