スーパーキューブの耐故障性について

• Item type: SIG Technical Reports(1)
• 公開日: 1996-09-13
• タイトル: スーパーキューブの耐故障性について
• タイトル / 言語: en
• タイトル: Highly Fault - Tolerant Routings and Diameter Vulnerability for the Supercube
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋工業大学電気情報工学科
• 著者所属: 名古屋工業大学電気情報工学科
• 著者所属: 名古屋工業大学電気情報工学科
• 著者所属: 名古屋工業大学電気情報工学科
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者名: 宮田, 和佳; 和田, 幸一; 陳, 慰; 川口, 喜三男
• 著者名(英): Kazuyoshi, Miyata; Koichi, Wada; Wei, Chen; Kimio, Kawaguchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では、計算機網を表すグラフに対する固定路線割当を取り扱う。ここで路線とは通信経路であり、固定路線割当とは一度決定した路線は変更されないことを意味する。グラフにおいてf個以内の点が故障しても、グラフ上の任意の2点間を結ぶ長さd以下の路線列が存在するならばこの路線割当は(，)?耐性であるという。本稿では、超立方体グラフを任意の点数に対して定義できるように拡張したスーパーキューブと呼ばれるグラフS_n（点数n（=2^s+)で連結度は)に対して、故障数が点連結度を越えた時もグラフが連結である場合には、(）辺のみが路線として定義されているならば(+3，s+B(?)?)?耐性となる。(）任意の全最短路線割当（任意の2点間に路線が定義されており、路線として最短路が定義される）に対して(，s+B(?)?)?耐性となる。(）(，s+B(?)?)?耐性となる最短路線割当が定義できることを示す。ここで、B(?)はh?1を2進数で表した時の1の個数を表す。また、S_nは任意の点に対して隣接する全ての点が故障しないならば、s+B(?)?1個の点が故障しても連結であることを示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Consider a communication network G in which a limited number of link and/or node fault F might occur. A routing ρ for the network (a fixed path between each pair of nodes) must be chosen without knowing which components might become faulty. The diameter of the surviving route graph R(F,ρ)/F, where two nonfaulty nodes are connected by an edge iff there are no faults on the route between them, could be one of the fault-tolerant measures for the routing ρ. In this paper, we show that we can construct efficient and highly fault-tolerant routings on an n-node supercube S_n such that the diameter of the surviving rout graph is bounded by a constant for the case that the number of faults is greater than the connectivity of S_n.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1996, 号 89(1996-AL-053), p. 63-70, 発行日 1996-09-13
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会