Set-To-Set Fault Tolerant Routing in Hypercubes (Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
In this paper, we give an algorithm which, given a set F of at most n-k faulty nodes, and two sets S={s_1,…,s_k} and T={t_1,…,t_k}, 1<k<n, of non-faulty nodes in n-dimensional hypercubes H_n, finds k fault-free node disjoint paths s_i→t_<ji>, where (j_i,…,j_k) is a permutation of (1,…,k), of length at most n+k in O (knlogk) time. The result of this paper implies that n disjoint paths of length at most 2n for set-to-set node disjoint path problem in H_n can be found in O (n^2logn) time.
- 社団法人電子情報通信学会の論文
- 1996-04-25
著者
-
Gu Qian
Department Of Computer Software The University Of Aizu
-
Peng Shietung
Department of Computer Software, The University of Aizu
-
Peng Shietung
Department Of Computer Software Distributed Parallel Processing Laboratory The University Of Aizu
-
OKAWA Satoshi
Department of Computer Software, The University of Aizu
-
Okawa Satoshi
Division Of Applied Life Sciences Graduate School Of Agriculture Kyoto University
-
Okawa S
Department Of Computer Software The University Of Aizu
-
Okawa Satoshi
Department Of Computer Software Of The University Of Aizu
関連論文
- Efficient algorithms for Disjoint Paths in Hypercubes and Star Networks
- Dyck Reductions are More Powerful Than Homomorphic Characterizations
- Homomorphic Characterizations Are More Powerful Than Dyck Reductions
- Subcellular Localization and Possible Functions of γ-Glutamyltransferase in the Radish (Raphanus sativus L.) Plant
- Purification and Properties of Soluble and Bound γ-Glutamyltransferases from Radish Cotyledon
- Occurrence of Two Forms of γ-Glutamyltransferases in Radish Plant
- 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
- Upper Bounds of the Correlation Functions of a Class of Binary Zero-Correlation-Zone Sequences(Coding Theory)
- Dyck Reductions of Minimal Linear Languages Yield the Full Class of Recursively Enumerable Languages
- Design of Array Processors for 2-D Discrete Fourier Transform (Special Issue on Parallel and Distributed Supercomputing)
- A Generalized Construction of Zero-Correlation Zone Sequence Set with Sequence Subsets
- 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
- A Ternary Zero-Correlation Zone Sequence Set Having Wide Inter-Subset Zero-Correlation Zone
- Circulating ApoE Level is Independently Associated with Urinary Albumin Excretion in Type 2 Diabetic Patients
- Calorie Restriction from a Young Age Preserves the Functions of Pancreatic β Cells in Aging Rats
- Tolosa-Hunt Syndrome Associated with Cytomegalovirus Infection