| 講演名 | 1999/4/23 3連結平面的グラフに対する最適な耐故障性ルーティング 永田 頼之, 陳 慰, 和田 幸一, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 通信網や計算機網において情報伝達の信頼性をいかに高めるかは重要な問題である。通常、通信網は局を頂点、通信回線を辺とした無向グラフで表される。2頂点間の通信はグラフ上の路を用いて行なわれ、路線と呼ばれるその通信路を決定することをルーティングと呼ぶ。ルーティングの耐故障性の評価尺度のひとつとして、頂点集合が通信網を表したグラフの故障していない頂点からなり、2頂点間の路線が定義されていて故障を含まないとき、その2頂点間に有向辺を持つグラフとして定義される生存路線グラフ(surviving route graph)の直径が提案されている。本稿では、三角形を持つ3連結平面グラフに対して、生存路線グラフの直径が最適となるようなルーティングを構成することができることを示す。 |
| 抄録(英) | We study the problem of designing fault-tolerant routings for a communication network which is triconnected planar network in the surviving route graph model. The surviving route graph for a graph G, a routing p and a set of faults F is a directed graph consisting of nonfault nodes with a directed edges from a node x to a node y if there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerant measures for the routing p. In this paper, we show that we can construct a routing for any triconnected planar graph with a triangle such that the diameter of the surviving route graph is optimal for any faults F(│F│ 2). |
| キーワード(和) | 平面的グラフ / ルーティング / 耐故障性 / グラフの直径 / 分散計算 |
| キーワード(英) | planar graph / routing / fault tolerance / diameter / distributed computing |
| 資料番号 | COMP99-3 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 1999/4/23(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 3連結平面的グラフに対する最適な耐故障性ルーティング |
| サブタイトル（和） | |
| タイトル（英） | An Optimal Fault-Tolerant Routing for Triconnected Planar Graphs |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 平面的グラフ / planar graph |
| キーワード(2)（和/英） | ルーティング / routing |
| キーワード(3)（和/英） | 耐故障性 / fault tolerance |
| キーワード(4)（和/英） | グラフの直径 / diameter |
| キーワード(5)（和/英） | 分散計算 / distributed computing |
| 第 1 著者 氏名（和/英） | 永田 頼之 / Yoriyuki Nagata |
| 第 1 著者 所属（和/英） | 名古屋工業大学電気情報工学科 Nagoya Institute of Technology |
| 第 2 著者 氏名（和/英） | 陳 慰 / Wei Chen |
| 第 2 著者 所属（和/英） | 名古屋工業大学電気情報工学科 Nagoya Institute of Technology |
| 第 3 著者 氏名（和/英） | 和田 幸一 / Koichi Wada |
| 第 3 著者 所属（和/英） | 名古屋工業大学電気情報工学科 Nagoya Institute of Technology |
| 発表年月日 | 1999/4/23 |
| 資料番号 | COMP99-3 |
| 巻番号（vol） | vol.99 |
| 号番号（no） | 30 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |