| 講演名 | 1997/3/17 故障があるアレンジメントグラフのブロードキャスティング 熊 亜平, 西谷 泰昭, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 本稿では,アレンジメントグラフに対する非適応型で最適な耐故障ブロードキャストスキーマを提案する。通信モデルはシングルポートモデルである。提案するスキーマは,(n,k)-アレンジメントグラフにおいて高々k(n-k)-1個の故障(頂点/辺)がある場合,漸近的に最適な時間でブロードキャストを実行できる。また,そのスキーマは, k(n-k)-1個の故障に耐えられる最適な非適応型スキーマと比較して,その計算時間の差が高々5k(n-k)+1である。 |
| 抄録(英) | In this paper, we propose a nonadaptive optimal fault tolerant broadcast scheme in arrangement graphs under the single-port communication model. The propsed scheme can tolerate up to k(n-k)-1 node and/or edge faults in the(n, k)-arrangement graph and completes a broadcast in an asymptotically optimal time. Our scheme takes at most 5k(n-k)+1 more time units than an optimal nonadaptive broadcast scheme that can tolerate k(n-k)-1 in the(n, k)-arrangement graph. |
| キーワード(和) | ネットワーク / ブロードキャスト / フォルトトレラント / アレンジメントグラフ |
| キーワード(英) | network / broadcast / fault tolerant / arrangement graph |
| 資料番号 | COMP96-84 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1997/3/17(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 故障があるアレンジメントグラフのブロードキャスティング |
| サブタイトル（和） | |
| タイトル（英） | Broadcasting in arrangement graphs with faults |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ネットワーク / network |
| キーワード(2)（和/英） | ブロードキャスト / broadcast |
| キーワード(3)（和/英） | フォルトトレラント / fault tolerant |
| キーワード(4)（和/英） | アレンジメントグラフ / arrangement graph |
| 第 1 著者 氏名（和/英） | 熊 亜平 / Yaping Xiong |
| 第 1 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Sience, Faculty of Engineering, Gunma University |
| 第 2 著者 氏名（和/英） | 西谷 泰昭 / Yasuaki Nishitani |
| 第 2 著者 所属（和/英） | 群馬大学工学部情報工学科 Department of Computer Sience, Faculty of Engineering, Gunma University |
| 発表年月日 | 1997/3/17 |
| 資料番号 | COMP96-84 |
| 巻番号（vol） | vol.96 |
| 号番号（no） | 585 |
| ページ範囲 | pp.- |
| ページ数 | 10 |
| 発行日 | |