Linear Time Algorithms for Fault Tolerant Routing in Hypercubes and Star Graphs

概要

論文の詳細を見る
In this paper, we study the following node-to-node fault tolerant routing problem : In the presence of up to n-1 faulty nodes, find a fault-free path which connects any two non-faulty nodes s and t in an n-connected graph. For node-to-node fault tolerant routing in n-dimensional hypercubes H_n, we give an algorithm which finds a fault-free path s → t of length at most d(s, t) + 2 ⌈ log n/(d(s, t)) ⌉ in O(n) time, where d(s, t) is the distance between s and t. We also show that a fault-free path s →t in H_n of length at most d(s, t) + 2i, 1 ≦ i < ⌈ log n/(d(s. t)) ⌉, can be found in O(d(s, t) n/(2^<i-1>)+n) time. For node-to-node fault tolerant routing in n-dimensional star graphs G_n, we give an algorithm which finds a fault-free path s → t of length at most min{d(G_n)+3, d(s, t)+6} in O(n) time, where d(G_n) = ⌊ (3(n-1))/2 ⌋ is the diameter of G_n. It is previously known that, in H_n, a fault-free path s → t of length at most d(s, t) for d(s, t) = n and at most d(s, t) + 2 for d(s, t) < n can be found in O(d(s, t)n) time, and in G_n, a fault-free path s → t of length at most min{d(G_n)+1, d(s, t)+4} can be found in O(d(s, t)n) time. When the time efficiency of finding the routing path is more important than the length of the path, the algorithms in this paper are better than the previous ones.
一般社団法人電子情報通信学会の論文
1995-09-25