| Presentation | 1994/9/22 k-Pairwise Cluster Fault Tolerant Routing in Hypercubes Qian-Ping Gu, Shietung Peng, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In this paper,we introduce a general fault-tolerant routing problem,cluster fault tolerant routing,which is a natural extension of the well studied node fault tolerant routing problem. A cluster is a connected subgraph of a graph G and a cluster is faulty if all nodes in it are faulty.Cluster fault tolerant(abbreviated as CFT in what follows)routing studies the number of fault clusters and the size(diameter)of the clusters that an interconnection network can tolerate in fault tolerant routing problems.In this paper,we investigate k-pairwise CFT routing in an n-dimensional hypercubes H_n.We give an O(n^2log n) time algorithm which finds the required routing paths for k- pairwise CFT routing in H_n.Our algorithm implies an O(n^2log n) algorithm for k-pairwise node disjoint path problem in H_n.The algorithm for k-pairwise node disjoint path problem in H_n significantly improves the previous results of time complexity O(n^ 3log n).As an extension of the fault diameter which is studied in node fault tolerant routing,we define cluster fault diameter for interconnection networks.We prove that the cluster fault diameter of H_n is n+2 when the diameters of the fault clusters are at most 1.We also show an O(n)time algorithm which finds a path of length at most n+3 for node-to-node CFT routing(k-pairwise CFT routing with k=1)in H_n. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Fault tolerant routing / interconnection networks / algorithms / node disjoint paths / fault diameter of graphs |
| Paper # | COMP94-42 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1994/9/22(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | k-Pairwise Cluster Fault Tolerant Routing in Hypercubes |
| Sub Title (in English) | |
| Keyword(1) | Fault tolerant routing |
| Keyword(2) | interconnection networks |
| Keyword(3) | algorithms |
| Keyword(4) | node disjoint paths |
| Keyword(5) | fault diameter of graphs |
| 1st Author's Name | Qian-Ping Gu |
| 1st Author's Affiliation | Department of Computer Software,The University of Aizu() |
| 2nd Author's Name | Shietung Peng |
| 2nd Author's Affiliation | Department of Computer Software,The University of Aizu |
| Date | 1994/9/22 |
| Paper # | COMP94-42 |
| Volume (vol) | vol.94 |
| Number (no) | 258 |
| Page | pp.pp.- |
| #Pages | 10 |
| Date of Issue | |