Set-To-Set Fault Tolerant Routing in Star Graphs*

Qian-Ping GU  Shietung PENG  

IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.4   pp.282-289
Publication Date: 1996/04/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
algorithm,  interconnection networks,  node disjoint paths,  fault tolerant routing,  

Full Text: PDF(598.8KB)>>
Buy this Article

In this paper, we give an algorithm which, given a set F of at most (n - 1) - k faulty nodes, and two sets S = {s1,..., sk} and T = {t1,..., tk}, 1 k n - 1, of nonfaulty nodes in n-dimensional star graphs Gn, finds k fault-free node disjoint paths si tji, where (j1,..., jk) is a permutation of (1,..., k), of length at most d(Gn) + 5 in O(kn) optimal time, where d(Gn) = 3(n-1)/2 is the diameter of Gn.