| 講演名 | 1998/12/4 パーミュテーショナルグラフのブロードキャスティング 田中 進也, 西谷 泰昭, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | パーミュテーショナルグラフと呼ばれる相互結合ネットワークに対する耐故障ブロードキャストスキーマを提案する.通信モデルは, 同期式, シングルポートモデルであり, クラッシュ型の故障を仮定している.提案するスキーマは, (n, k)-パーミュテーショナルグラフにおいて高々n-2個の故障(頂点, 辺)がある場合にもブロードキャストが可能であり, 耐故障性については最適である.また, その計算時間は漸近的に最適であり, n-2の耐故障性を持つブロードキャストスキーマの計算時間の下限と比較して, その差は高々4n-3である. |
| 抄録(英) | We propose a fault tolerant broadcast scheme in the permutational graphs. Communicational model is synchronous and the single-port model, and we assume that its fault type is crash type. The proposed scheme can broadcast in the (n, k)-permutational graph with n-2 node and/or edge faults, thus it is optimal for fault tolerance. Our scheme takes at most 4n-3 more time units than an optimal broadcast scheme that can tolerate n-2 faults in the (n, k)-permutational graph. |
| キーワード(和) | ネットワーク / ブロードキャスト / 耐故障性 / パーミュテーショナルグラフ / (n, k)-スターグラフ |
| キーワード(英) | network / broadcasting / fault tolerance / permutational graph / (n, k)-star graph |
| 資料番号 | COMP98-65 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1998/12/4(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | パーミュテーショナルグラフのブロードキャスティング |
| サブタイトル（和） | |
| タイトル（英） | A broadcasting algorithm in permutational graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ネットワーク / network |
| キーワード(2)（和/英） | ブロードキャスト / broadcasting |
| キーワード(3)（和/英） | 耐故障性 / fault tolerance |
| キーワード(4)（和/英） | パーミュテーショナルグラフ / permutational graph |
| キーワード(5)（和/英） | (n, k)-スターグラフ / (n, k)-star graph |
| 第 1 著者 氏名（和/英） | 田中 進也 / Shinya Tanaka |
| 第 1 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Science Faculty of Engineering, Gunma University |
| 第 2 著者 氏名（和/英） | 西谷 泰昭 / Yasuaki Nishitani |
| 第 2 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Science Faculty of Engineering, Gunma University |
| 発表年月日 | 1998/12/4 |
| 資料番号 | COMP98-65 |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 442 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |