| Presentation | 2004/7/23 Fault-tolerant routing algorithm in bubble-sort graphs Yasuto SUZUKI, Keiichi KANEKO, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | An n-dimensional bubble-sort graph is a graph which is regular and symmetric. It has n! nodes and (n - l)n!/2 edges while its connectivity and diameter are n - 1, n(n - l)/2, respectively. Much attention is paid to a bubble-sort graph because of its simple and regular structure. In this paper, for an n-bubble-sort graph, we give an O(n^5)-time algorithm that solves the node-to-set disjoint paths problem: given a node s and a node set D = (d_1, d_2, ・・・) d_k} in a k-connected graph, find k internally disjoint paths between s and each d_i's in D. Once this problem solved, in the communication between s and d, at least one node can receive the massage even if the topology has k - 1 faulty edges and/or nodes. We also show that the total length of n - 1 paths given by the algorithm is of O(n^3). The simulation results show that the average time complexity of the algorithm and the average total length of the paths given by the algorithm are of O(n^<4.7>) and O(n^3), respectively. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | bubble-sort graph / disjoint paths / multicast / fault tolerance / polynomial-order algorithm |
| Paper # | DC2004-13 |
| Date of Issue |
| Conference Information | |
| Committee | DC |
|---|---|
| Conference Date | 2004/7/23(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 | Dependable Computing (DC) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Fault-tolerant routing algorithm in bubble-sort graphs |
| Sub Title (in English) | |
| Keyword(1) | bubble-sort graph |
| Keyword(2) | disjoint paths |
| Keyword(3) | multicast |
| Keyword(4) | fault tolerance |
| Keyword(5) | polynomial-order algorithm |
| 1st Author's Name | Yasuto SUZUKI |
| 1st Author's Affiliation | Faculty of Technology, Tokyo University of Agriculture and Technology() |
| 2nd Author's Name | Keiichi KANEKO |
| 2nd Author's Affiliation | Faculty of Technology, Tokyo University of Agriculture and Technology |
| Date | 2004/7/23 |
| Paper # | DC2004-13 |
| Volume (vol) | vol.104 |
| Number (no) | 239 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |