ATM通信網に対するグラフ理論的モデル化と効率と耐故障性の評価尺度に関する研究

(1)ATM網をモデル化した固定ルーティングと拡張超立方体とスーパーキューブの耐故障性ATM網のグラフ理論的モデル化としてルーティングを含めた耐故障性を定量的に評価する固定ルーティングのモデルを拡張し、そのモデルのもとで通信効率と故障耐性に優れた計算機網として拡張超立方体C(d,k)とn点スーパーキューブS_nをとりあげこのグラフに対してその連結度を越える故障を起こしても、効率的に通信ができるようなルーティングを構成した。拡張超立方体は通常の超立方体よりも通信効率と故障耐性に優れている。スーパーキューブは超立方体グラフの長所を残したまま唯一の欠点である点数が2つ冪乗でしか定義できない欠点を補ったグラフである。これらの結果は拡張超立方体に関しては研究発表の(6)でスーパーキューブに関しては研究発表の(1)で発表した。また、同様のモデルのもとで2連結グラフに対する最適なルーティングをATM網に適するように改良した(研究発表の(4))。(2)固定ルーティング構成のためのグラフの分割(1)で定義された固定ルーティングにおいて、一般的な計算機網に対する耐故障性の高いルーティングを構成するためには、グラフのk-分割問題はと呼ばれる計算機網に対応するグラフの分割ができればよいことを筆者らは示した。グラフのk-分割問題(a)連結無向グラフG=(V,E)、(b)k個の異なる点a_1,……,a_k、(c)Σ^k_<i=1>n_i=|V|となるk個の自然数n_1,……,n_kととなる入力に対して、点集合Vの分割V_1,……,V_kで各V_iがa_iを含み、その要素数がn_iとなりV_iは連結グラフを誘導するものを求める問題である。この問題は一般にはNP完全であり、入力グラフがk-連結ならば必ず解が存在することが知られているがk=2,3の場合を除いて解を求める多項式時間のアルゴリズムは知られていない。固定ルーティングの構成のためにはグラフのk-分割問題をそのまま解く必要はなく、ここではグラフのk-分割問題を変形した問題を提案しそれらを解く多項式時間アルゴリスムを与え、固定ルーティング構成に利用できることを示した(研究発表の(3),(5))。

(1)ATM網をモデル化した固定ルーティングと拡張超立方体とスーパーキューブの耐故障性ATM網のグラフ理論的モデル化としてルーティングを含めた耐故障性を定量的に評価する固定ルーティングのモデルを拡張し、そのモデルのもとで通信効率と故障耐性に優れた計算機網として拡張超立方体C(d,k)とn点スーパーキューブS_nをとりあげこのグラフに対してその連結度を越える故障を起こしても、効率的に通信ができるようなルーティングを構成した。拡張超立方体は通常の超立方体よりも通信効率と故障耐性に優れている。スーパーキューブは超立方体グラフの長所を残したまま唯一の欠点である点数が2つ冪乗でしか定義できない欠点を補ったグラフである。これらの結果は拡張超立方体に関しては研究発表の(6)でスーパーキューブに関しては研究発表の(1)で発表した。また、同様のモデルのもとで2連結グラフに対する最適なルーティングをATM網に適するように改良した(研究発表の(4))。(2)固定ルーティング構成のためのグラフの分割(1)で定義された固定ルーティングにおいて、一般的な計算機網に対する耐故障性の高いルーティングを構成するためには、グラフのk-分割問題はと呼ばれる計算機網に対応するグラフの分割ができればよいことを筆者らは示した。グラフのk-分割問題(a)連結無向グラフG=(V,E)、(b)k個の異なる点a_1,……,a_k、(c)Σ^k_<i=1>n_i=|V|となるk個の自然数n_1,……,n_kととなる入力に対して、点集合Vの分割V_1,……,V_kで各V_iがa_iを含み、その要素数がn_iとなりV_iは連結グラフを誘導するものを求める問題である。この問題は一般にはNP完全であり、入力グラフがk-連結ならば必ず解が存在することが知られているがk=2,3の場合を除いて解を求める多項式時間のアルゴリズムは知られていない。固定ルーティングの構成のためにはグラフのk-分割問題をそのまま解く必要はなく、ここではグラフのk-分割問題を変形した問題を提案しそれらを解く多項式時間アルゴリスムを与え、固定ルーティング構成に利用できることを示した(研究発表の(3),(5))。