通信網に対する高信頼性最適路線割当ての存在条件と計算量の改善

概要

論文の詳細を見る
本論文は,通信網を表すグラフに対する両方向性固定路線割当て(bidirectional fixed graph routing)を取り扱う.路線(route)とは通信経路である,両方向性とは1本の路線を両方向の通信に使用することである.また固定とは路線割当てが変更されないことを意味する.グラフにおいてk-1個以内の要素を除去(通信網における故障に対応する)しても,グラフ上の任意の2点間を結ぶ長さd以内の路線列(route sequence)が存在するならば,この路線割当は(d,k-1)-耐性でいると言い,特に(2,k-1)-耐性の路線割当ては最適である.従来,ある正定数のc_4に対してn/log_2n≧c_1k^3を満たすn点k-連結グラフについては,(2,k-1)-耐性の両方向性路線割当てが構成可能であり,k-連結グラフのk分割問題を解くための計算時間を除外するならば,路線割当て時間はO(n^<2.5>k^3log_2n)であることが知られていた.また,ある正定数のc_4に対してn/log_2n≧c_1k^3を満たすn点k-辺連結グラフについては,辺のみの故障に対して(2,k-1)-耐性の両方向性路線割当がO(n^<2.5>k^3log_2n)時間で構成可能であることが知られていた.本論文は,従来の点数条件および計算時間を改善し,n点k-連結グラフがある正定数C_3に対し条件n≧C_3K^3を満たすならば,(2,k-1)-耐性の両方向性路線割当てが構成でき,k-連結グラフのk分割問題を解くための計算時間を除外すればO(n^<2.5>k^2)時間で計算でき,特にk=3のときは,3分割問題を解くための計算時間も含めてO(n^2)時間で構成できること,n点k-辺連結グラフがある正定数c_4に対し条件n≧C_4k^3を満たすならば,辺のみの故障に対し(2,k-1)-耐性の両方向性路線割当てがO(n^<2.5>k^2)時間で構成できること,更に3-辺連結グラフに対しては点数条件と路線割当て計算時間に関し3-連結グラフに対するのと同じ結果が得られることを示す.
社団法人電子情報通信学会の論文
1993-06-25

通信網に対する高信頼性最適路線割当ての存在条件と計算量の改善

スポンサーリンク

概要

著者

関連論文

スポンサーリンク