| Presentation | 1994/10/21 Cluster Fault Tolerant Routing in Star Graphs 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 study the node fault tolerant routing properties of n-dimensional star graphs G_nbased on the cluster fault tolerant routing model which is a natural extension of the well studied node fault tolerant routing.For a graph G,a cluster C is a connected subgraph of G,and C is called fault cluster if all nodes in C are faulty.In cluster fault tolerant routing,the number of fault clusters and the size of the fault clusters that can be tolerated are studied.For node-to-node,node-to-set,set-to-set,and k-pairwise fault tolerant routing problems in n-dimensional star graphs G_n,we prove that G_n can tolerate n - 2,n - 1 - k,n - 1 - k,and n - 2k fault clusters of diameter at most 2,respectively.Our results show that stax graphs G_nhave very good node fault tolerant routing properties.Wealso give optimal time algorithms which find the required routing paths of length d(G_n)+ O(1)for any tolerable set of fault clusters in the above routing problems, where d(G_n)=[(3(n-1)), 2]is the diameter of G_n. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Node fault tolerant Routing / Algorithm / Interconnection network / Node Disjoint Path |
| Paper # | COMP94-49 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1994/10/21(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) | Cluster Fault Tolerant Routing in Star Graphs |
| Sub Title (in English) | |
| Keyword(1) | Node fault tolerant Routing |
| Keyword(2) | Algorithm |
| Keyword(3) | Interconnection network |
| Keyword(4) | Node Disjoint Path |
| 1st Author's Name | Qian-Ping Gu |
| 1st Author's Affiliation | The University of Aizu() |
| 2nd Author's Name | Shietung Peng |
| 2nd Author's Affiliation | The University of Aizu / |
| Date | 1994/10/21 |
| Paper # | COMP94-49 |
| Volume (vol) | vol.94 |
| Number (no) | 304 |
| Page | pp.pp.- |
| #Pages | 10 |
| Date of Issue | |