| 講演名 | 2002/8/15 焦げたパンケーキグラフにおける節点から節点集合への互いに素な経路問題 金子 敬一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 焦げたパンケーキグラフ(burnt pancake graph)は,ケイリー(Cayley)グラフの一種であり,同程度の数の節点からなるハイパキューブ(hypercube)などと比較して,次数(degree),直径(diameter)とも小さく,超並列システムなどの位相として適している。しかしながら,焦げたパンケーキグラフは,パンケーキグラフ(pancake graph)同様,直径の正確な値や次数の多項式時間で2節点間の最短経路を求める算法なども未知であり,研究の余地が大きい.このため,本研究では,次数nの焦げたパンケーキグラフを対象とし,その次数nの多項式オーダの時間で,1つの出発節点とn個の目的節点に対して,出発節点を除いて互いに素なn本の経路を求める算法を提案する.この算法では,まず類(class)という概念を導入し,すべての節点を類に分類する.次に,焦げたパンケーキグラフの再帰構造を利用し,目的節点のうちn-1個に対して,出発節点が属する部分グラフにおける子問題へと帰着する.残りの1つの節点に対しては,特定の類に属する節点のみからなる類の経路を使って,他の経路と互いに素な経路を構成する.また,算法の正しさの証明とともに,計算量および得られる経路長の総和のオーダを見積もって示す.さらに,計算機シミュレーションにより提案算法の性能評価を行い,その結果を報告する. |
| 抄録(英) | 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. |
| キーワード(和) | 焦げたパンケーキグラフ / 互いに素な経路 / 多項式算法 / 耐故障性 |
| キーワード(英) | Burnt Pancake Graphs / Disjoint Paths / Polynomial Algorithm / Fault Tolerance |
| 資料番号 | DC2002-16 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DC |
|---|---|
| 開催期間 | 2002/8/15(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Dependable Computing (DC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 焦げたパンケーキグラフにおける節点から節点集合への互いに素な経路問題 |
| サブタイトル（和） | |
| タイトル（英） | An Algorithm for the Node-to-Set Disjoint Paths Problem in Burnt Pancake Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 焦げたパンケーキグラフ / Burnt Pancake Graphs |
| キーワード(2)（和/英） | 互いに素な経路 / Disjoint Paths |
| キーワード(3)（和/英） | 多項式算法 / Polynomial Algorithm |
| キーワード(4)（和/英） | 耐故障性 / Fault Tolerance |
| 第 1 著者 氏名（和/英） | 金子 敬一 / Keiichi KANEKO |
| 第 1 著者 所属（和/英） | 東京農工大学工学部 Faculty of Technology, Tokyo University of Agriculture and Technology |
| 発表年月日 | 2002/8/15 |
| 資料番号 | DC2002-16 |
| 巻番号（vol） | vol.102 |
| 号番号（no） | 262 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |