2026-05-20T00:47:04Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00032273 2025-01-19T22:36:32Z 1164:2592:2672:2674

スーパーキューブの耐故障性について Highly Fault - Tolerant Routings and Diameter Vulnerability for the Supercube 宮田, 和佳 和田, 幸一 陳, 慰 川口, 喜三男 Kazuyoshi, Miyata Koichi, Wada Wei, Chen Kimio, Kawaguchi 本稿では、計算機網を表すグラフに対する固定路線割当を取り扱う。ここで路線とは通信経路であり、固定路線割当とは一度決定した路線は変更されないことを意味する。グラフにおいて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個の点が故障しても連結であることを示す。 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. technical report 情報処理学会 1996-09-13 application/pdf 情報処理学会研究報告アルゴリズム（AL） 89(1996-AL-053) 1996 63 70 AN1009593X https://ipsj.ixsq.nii.ac.jp/record/32273/files/IPSJ-AL96053009.pdf jpn