| 講演名 | 2004/7/23 バブルソートグラフにおける耐故障経路選択アルゴリズム(2004年並列/分散/協調処理に関する「青森」サマーワークショップ(SWoPP青森2004)) 鈴木 康斗, 金子 敬一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | n-バブルソートグラフは,正則かつ対称なグラフであり,その頂点数,辺数,連結度,直径はそれぞれn!,(n-l)n!/2,n-1,(n-1)/2である.単純で対称な構造をしていることから注目を集めている.本稿では,n-バブルソートグラフを対象とし,頂点から頂点集合への互いに素な経路問題:k-連結グラフにおいて,頂点sと頂点集合D = {d_1:d_2,・・・,d_k}が与えられたとき,sを除いて互いにk本のsからd_i(1≦i≦k)への経路を求めよ;をO(n^5)の時間で解くアルゴリズムを提案する。sからD中のk個の頂点へ向けてマルテキャストを行う際,高々k-1個の停止型故障(辺または頂点)があっても,少くともひとつの頂点はsからのメッセージを受信可能である,という耐故障性をこの問題の解決により達成できる.さらに本稿では,提案されたアルゴリズムが与える経路の長さの総和がO(n^3)であることもあわせて示す.計算機シミュレーションの結果,平均時間計算量,経路長の総和の平均はそれぞれ0(n^<4.7>),0(n^3)となった. |
| 抄録(英) | An n-dimensional bubble-sort graph is a graph which is regular and symmetric. It has n! nodes and (n - l)n!/2 edges while its connectivity and diameter are n - 1, n(n - l)/2, respectively. Much attention is paid to a bubble-sort graph because of its simple and regular structure. In this paper, for an n-bubble-sort graph, we give an O(n^5)-time algorithm that solves the node-to-set disjoint paths problem: given a node s and a node set D = (d_1, d_2, ・・・) d_k} in a k-connected graph, find k internally disjoint paths between s and each d_i's in D. Once this problem solved, in the communication between s and d, at least one node can receive the massage even if the topology has k - 1 faulty edges and/or nodes. We also show that the total length of n - 1 paths given by the algorithm is of O(n^3). The simulation results show that the average time complexity of the algorithm and the average total length of the paths given by the algorithm are of O(n^<4.7>) and O(n^3), respectively. |
| キーワード(和) | バブルソートグラフ / 素な経路 / マルチキャスト / 耐故障性 / 多項式オーダアルゴリズム |
| キーワード(英) | bubble-sort graph / disjoint paths / multicast / fault tolerance / polynomial-order algorithm |
| 資料番号 | DC2004-13 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DC |
|---|---|
| 開催期間 | 2004/7/23(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Dependable Computing (DC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | バブルソートグラフにおける耐故障経路選択アルゴリズム(2004年並列/分散/協調処理に関する「青森」サマーワークショップ(SWoPP青森2004)) |
| サブタイトル（和） | |
| タイトル（英） | Fault-tolerant routing algorithm in bubble-sort graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | バブルソートグラフ / bubble-sort graph |
| キーワード(2)（和/英） | 素な経路 / disjoint paths |
| キーワード(3)（和/英） | マルチキャスト / multicast |
| キーワード(4)（和/英） | 耐故障性 / fault tolerance |
| キーワード(5)（和/英） | 多項式オーダアルゴリズム / polynomial-order algorithm |
| 第 1 著者 氏名（和/英） | 鈴木 康斗 / Yasuto SUZUKI |
| 第 1 著者 所属（和/英） | 東京農工大学工学部 Faculty of Technology, Tokyo University of Agriculture and Technology |
| 第 2 著者 氏名（和/英） | 金子 敬一 / Keiichi KANEKO |
| 第 2 著者 所属（和/英） | 東京農工大学工学部 Faculty of Technology, Tokyo University of Agriculture and Technology |
| 発表年月日 | 2004/7/23 |
| 資料番号 | DC2004-13 |
| 巻番号（vol） | vol.104 |
| 号番号（no） | 239 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |