拡張超立方体グラフに対する耐故障性路線割当と直径罹障度

概要

論文の詳細を見る
本稿では、計算機網を表すグラフに対する固定路線割当を取り扱う。ここで、路線とは通信経路であり、固定路線割当とは一度決定した路線は変更されないことを意味する。グラフにおいてf個以内の点が故障しても、グラフ上の任意の2点間を結ぶ長さd以内の路線列が存在するならば、この路線割当は(d,f)-耐性であるという。本稿では、超立体グラフC(d,k)(d^k個の点を持ち、点はk桁のd進数で表され、正確に1桁が異なる2点間に辺が存在するグラフであり、点連結果は(d-1)kとなる。またd=2の場合が通常の超立方体グラフに相当する)に対して故障数が点連結度を越えた時でもグラフが連結である場合には、(1)辺のみが路線として定義されているならば(k+2,2(d-1)k-d-1)-耐性となる、(2)任意の全最短路線割当(任意の2点間に路線が定義されており、最短路が定義される路線割当)に対して(6,2(d-1)k-d-1)-耐性となる、(3)(4,2(d-1)k-d-1)-耐性となる最短路線淡当が定義できることなどを示す。
社団法人電子情報通信学会の論文
1994-11-18