| Presentation | 2003/7/30 Node-to-Node Internally Disjoint Paths Problem in Bubble-Sort Graphs Keiichi KANEKO, Yasuto SUZUKI, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A bubble-sort graph is a variant of Cayley graphs and it is suitable as a toplogy for massively parallel systems because of its simple and regular structure. Therefore, in this study, we focus on nth bubble-sort graphs and propose an algorithm to obtain n-1 disjoint paths between arbitrary two nodes in polynomial order of n which is the degree of the graph plus one. We estimate the time complexity of the algorithm and the sum of path lengths after proving the correctness of the algorithm. Moreover, we report the results of computer experiment to evaluate average performance of the algorithm. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Bubble-Sort Graphs / Internaly Disjoint Paths / Polynomial Algorithm / Fault Tolerance |
| Paper # | DC2003-12 |
| Date of Issue |
| Conference Information | |
| Committee | DC |
|---|---|
| Conference Date | 2003/7/30(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) | Node-to-Node Internally Disjoint Paths Problem in Bubble-Sort Graphs |
| Sub Title (in English) | |
| Keyword(1) | Bubble-Sort Graphs |
| Keyword(2) | Internaly Disjoint Paths |
| Keyword(3) | Polynomial Algorithm |
| Keyword(4) | Fault Tolerance |
| 1st Author's Name | Keiichi KANEKO |
| 1st Author's Affiliation | Faculty of Technology, Tokyo University of Agriculture and Technology() |
| 2nd Author's Name | Yasuto SUZUKI |
| 2nd Author's Affiliation | Faculty of Technology, Tokyo University of Agriculture and Technology |
| Date | 2003/7/30 |
| Paper # | DC2003-12 |
| Volume (vol) | vol.103 |
| Number (no) | 250 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |