| Presentation | 2002/8/15 An Algorithm for the Node-to-Set Disjoint Paths Problem in Burnt Pancake Graphs Keiichi KANEKO, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A burnt pancake graph is a variant of Cayley graphs and it is suitable as a toplogy for massively parallel systems because its degree and diameter are smaller than a hypercube which has similar number of nodes. However, in a burnt pancake graph, its precise diameter or an algorithm to obtain shortest paths in polynomial time of the degree are still unknown like pancake graphs. So, there is much room for further researches. Hence, in this study, we focus on n-burnt pancake graphs and propose an algorithm to obtain n disjoint paths from a source node to n destination nodes in polynomial order of n which is the degree of the graph. In the algorithm, a notion of a class is introduced and all nodes are classified into classes. Next, the algorithm takes advantage of the recursive structure of a burnt pancake graph, and reduces the generation of paths to n - 1 destination nodes to the subproblem in the burnt pancake subgraph to which the source node belongs. The path to the remaining one destination node which is disjoint to other paths is obtained by using a path whose nodes belong to a specific class. In addition, 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 simulation to evaluate average performance of the algorithm. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Burnt Pancake Graphs / Disjoint Paths / Polynomial Algorithm / Fault Tolerance |
| Paper # | DC2002-16 |
| Date of Issue |
| Conference Information | |
| Committee | DC |
|---|---|
| Conference Date | 2002/8/15(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) | An Algorithm for the Node-to-Set Disjoint Paths Problem in Burnt Pancake Graphs |
| Sub Title (in English) | |
| Keyword(1) | Burnt Pancake Graphs |
| Keyword(2) | 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() |
| Date | 2002/8/15 |
| Paper # | DC2002-16 |
| Volume (vol) | vol.102 |
| Number (no) | 262 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |