Set-To-Set Fault Tolerant Routing in Star Graphs
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we give an algorithm which, given a set F of at most (n-1)-k faulty nodes, and two sets S={s_1,...,s_k} and T={t_1,...,t_k}, 1≦k≦n-1, of non-faulty nodes in n-dimensional star graphs G_n, finds k fault-free node disjoint paths s_i→t_<j_i>, where (j_1,...,j_k) is a permutation of (1,...,k), of length at most d(G_n) + 5 in Ο(kn) optimal time, where d(G_n)=⌊(3(n-1))/2⌋ is the diameter of G_n.
- 一般社団法人電子情報通信学会の論文
- 1996-04-25
著者
-
Gu Qian-ping
Department Of Computer Software The University Of Aizu
-
Peng Shietung
Department Of Computer Software Distributed Parallel Processing Laboratory The University Of Aizu
関連論文
- A Parallel Algorithm for the Longest Path Problem on Acyclic Graphs with Integer Arc Lengths
- Efficient algorithms for Disjoint Paths in Hypercubes and Star Networks
- Efficient Algorithms for Node Disjoint Path Problems
- Set-To-Set Fault Tolerant Routing in Hypercubes (Special Section on Discrete Mathematics and Its Applications)
- d-Separated Paths in Hypercubes and Star Graphs
- Design of Array Processors for 2-D Discrete Fourier Transform (Special Issue on Parallel and Distributed Supercomputing)
- Distributed Algorithms for Leader Election on Partially Ordered Keys (特集 マルチメディア通信プロトコル)
- Fault Tolerant Routing in Toroidal Networks (Special Issue on Architectures, Algorithms and Networks for Massively parallel Computing)
- Set-To-Set Fault Tolerant Routing in Star Graphs
- Efficient Broadcasting Algorithms in Faulty Hypercubes and Star Graphs
- Node-to-Set Disjoint Paths with Optimal Length in Star Graphs (Special Issue on Parallel and Distributed Supercomputing)
- Linear Time Algorithms for Fault Tolerant Routing in Hypercubes and Star Graphs