| 講演名 | 2005/7/29 焦げたパンケーキグラフの内素な経路問題(高信頼システム, SWOPP武雄2005(2005年並列/分散/協調処理に関する「武雄」サマー・ワークショップ)) 澤田 直樹, 鈴木 康斗, 金子 敬一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 次数nの焦げたパンケーキグラフ[1]は, n!×2^n個の節点を持ったグラフであり, ハイパーキューブなどと比べて集積度が高いこと, パンケーキグラフやスターグラフ, ローテータグラフなどとは異なる節点数を結合できることから, 相互結合網の位相として注目を集めている.本研究では, 焦げたパンケーキグラフの任意の2節点に対して, 次数の多項式時間で, 次数と同じ本数の内素な経路を作成するアルゴリズムを提案する.さらに本稿では, 提案された算法が与える時間計算量と最大経路長が, それぞれO(n^3)および3n+4であることもあわせて示す.計算機シミュレーションの結果, 平均時間計算量, 最大経路長はそれぞれO(n^<2.6>), 3n+4となった. |
| 抄録(英) | An n-burnt pancake graph B_n[1] is an undirected regular graph with n!×2^n nodes and degree n. The burnt pancake graphs is an attractive as a topology of interconnection networks. Because the density of B_n is higher than that of hypercube and B_n can interconnect different numbers of nodes from the pancake graphs, the star graphs and the rotator graphs. In this study, we take an n-burnt pancake graph as a target and propose an algorithm to obtain, for any pair of nodes, n internally disjoint paths between them in the time complexity of polynomial order of the degree. We also show that the time complexity and the max length of a path given by the algorithm is O(n^3) and 3n+4, respectively. The simulation results show that the average time complexity of the altorithm and the max length of a path given by the algorithm are of O(n^<2.6>) and 3n+4, respectively. |
| キーワード(和) | 焦げたパンケーキグラフ / 内素な経路 / 耐故障性 / 多項式オーダ算法 |
| キーワード(英) | burnt pancake graph / disjoint paths / fault tolerance / polynomial-order algorithm |
| 資料番号 | DC2005-13 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DC |
|---|---|
| 開催期間 | 2005/7/29(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Dependable Computing (DC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 焦げたパンケーキグラフの内素な経路問題(高信頼システム, SWOPP武雄2005(2005年並列/分散/協調処理に関する「武雄」サマー・ワークショップ)) |
| サブタイトル（和） | |
| タイトル（英） | An Algorithm for Node-Disjoint Paths Problem in Burnt Pancake Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 焦げたパンケーキグラフ / burnt pancake graph |
| キーワード(2)（和/英） | 内素な経路 / disjoint paths |
| キーワード(3)（和/英） | 耐故障性 / fault tolerance |
| キーワード(4)（和/英） | 多項式オーダ算法 / polynomial-order algorithm |
| 第 1 著者 氏名（和/英） | 澤田 直樹 / Naoki SAWADA |
| 第 1 著者 所属（和/英） | 東京農工大学工学部 Department of Technology, Tokyo University of Agriculture and Technology |
| 第 2 著者 氏名（和/英） | 鈴木 康斗 / Yasuto SUZUKI |
| 第 2 著者 所属（和/英） | 東京農工大学工学部 Department of Technology, Tokyo University of Agriculture and Technology |
| 第 3 著者 氏名（和/英） | 金子 敬一 / Keiichi KANEKO |
| 第 3 著者 所属（和/英） | 東京農工大学工学部 Department of Technology, Tokyo University of Agriculture and Technology |
| 発表年月日 | 2005/7/29 |
| 資料番号 | DC2005-13 |
| 巻番号（vol） | vol.105 |
| 号番号（no） | 227 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |