122
Views
6
CrossRef citations to date
0
Altmetric
Original Articles

Conditional fault-tolerant routing of (n, k)-star graphs

, &
Pages 1695-1707 | Received 16 Dec 2014, Accepted 29 Jun 2015, Published online: 10 Aug 2015
 

Abstract

As a generalization of the star graph, the (n,k)-star graph is one of the most important interconnection networks for parallel and distributed computing system. In this paper, we investigate the fault-tolerant routing problem of (n,k)-star graphs under the conditional fault assumption (CFA), where all the neighbours of any fault-free node cannot be faulty simultaneously. We show that, under the CFA, the (n,k)-star graph can tolerate up to n+k4 faulty nodes, and there is a fault-free path of length at most the diameter of the (n,k)-star graph plus 6 between any two fault-free nodes.

2010 AMS Subject Classifications:

Disclosure Statement

No potential conflict of interest was reported by the authors.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.