| Presentation | 2006/7/25 Incomplete Pancake Graphs and their Routing Problems Keiichi KANEKO, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | A pancake graph was proposed as a topology for interconnection networks of parallel computers, and it has a merit that it can connect many nodes with small diameter and small degree. However, the number of nodes in a pancake graph must be equal to the factorial of an integer, which causes a demerit that it lacks incremental expandability. Hence, in this paper, we propose a graph that is obtained by deleting some of sub graphs of a pancake graph, and give algorithms for solving the unicast routing problem, Hamiltonian cycle problem, and the container problem. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | incomplete pancake graphs / unicast routing / Hamiltonian cycles / Hamiltonian paths / container problem / fault tolerance |
| Paper # | DC2006-20 |
| Date of Issue |
| Conference Information | |
| Committee | DC |
|---|---|
| Conference Date | 2006/7/25(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) | Incomplete Pancake Graphs and their Routing Problems |
| Sub Title (in English) | |
| Keyword(1) | incomplete pancake graphs |
| Keyword(2) | unicast routing |
| Keyword(3) | Hamiltonian cycles |
| Keyword(4) | Hamiltonian paths |
| Keyword(5) | container problem |
| Keyword(6) | fault tolerance |
| 1st Author's Name | Keiichi KANEKO |
| 1st Author's Affiliation | Institute of Symbiotic Science and Technology Tokyo University of Agriculture and Technology() |
| Date | 2006/7/25 |
| Paper # | DC2006-20 |
| Volume (vol) | vol.106 |
| Number (no) | 198 |
| Page | pp.pp.- |
| #Pages | 5 |
| Date of Issue | |