（n，k） －多重サイクルグラフに対する （3，k - 1） －耐性かつ両方向性の最短路線割当

• Item type: SIG Technical Reports(1)
• 公開日: 1988-05-26
• タイトル: （n，k） －多重サイクルグラフに対する （3，k - 1） －耐性かつ両方向性の最短路線割当
• タイトル / 言語: en
• タイトル: The (3, k - l) -tolerant, bidirectional and miniml - 1ength routings on (n, k) -multi - cycle graphs
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋工業大学工学部
• 著者所属: 名古屋工業大学工学部
• 著者所属: 名古屋工業大学工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering, Nagoya Institute of Technology
• 著者名: 羅予頻; 川口, 喜三男; 和田, 幸一
• 著者名(英): Yupin, Luo; Kimio, Kawaguchi-Izawa; Koich, Wada
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 信頼性が高く効率のよい通信（計算機）網をいかに実現するかは重要な問題である．これを，本論文は，交換設備或は計算機を点，通信線を辺に対応させたグラフそのものとその上の路線割当(routing)をいかに構成するかと言う問題として扱う．路線割当が前もって計算されている通信網の信頼性と効率の尺度として，通信網を表すグラフの故障していない点及び二点間の路線(route)が故障を含まないときその間に有向辺をもつ有向グラフとして定義されるSR?グラフの直径を用いる．通信網上に故障が存在するとき，これらの故障を回避して高々SR?グラフの直径に等しい数の無故障の路線を接続して通信を行うことができるからである．本論文は，与えられたnとk(n>k≧2)に対して，(k-1)個以下の任意の故障に対するSR?グラフの直径が3以下となる辺数最小のn点グラフ（(n k)?多重サイクルグラフ）とその上の両方向且つ最短な路線割当が構成できることを示す．この路線割当は(n k)?多重サイクルグラフ上の最も効率のよい両方向最短路線割当である．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A fixed routing ρ for a network G must be defined without knowing where fault might occur. Let F be a set of faulty elements G. The diameter (denoted by DIAM(R(G,ρ)/F)) of the surviving route graph R(G,ρ)/F, of which nodes are corresponding to the nonfaulty nodes of G and edges to the nonfaulty routes of G, could be one of the fault-tolerance measures for the routing ρ. In this paper, given any n and k (n>k≧2), we show that a bidirectional and minimal length routing ρ can be constructed on a (n,k)-multi-cycle graph M(n,k) such that DIAM(R(M(n,k),ρ)/F) is at most 3 if IFI ≦K-1.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10485570
• 書誌情報: 情報処理学会研究報告プログラミング（PRO）; 巻 1988, 号 37(1988-PRO-025), p. 99-108, 発行日 1988-05-26
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会