直径の小さいグラフとその上の耐故障性路線割当ての構成

概要

論文の詳細を見る
通信網や計算機網における情報伝達の信頼性をいかに経済的に効率良く高めるかは重要な問題である．通常，通信網（計算機網）は局（計算機）を点，通信回線を辺とした無向または有向グラフで表されるが，本論文では，2方向性通信回線をモデル化した無向グラフ（以下，グラフと呼ぶ）を考える．通信網における任意の2点間の通信はグラフの道を用いて行われる．通信網の2点間の通信経路をたかだか一つ決定することを路線割当て（routing）と呼ぶが，路線割当てが前もって計算されている通信網の信頼性の尺度として，通信網を表すグラフとその路線割当ておよび，故障点と故障辺により定義されるSR-グラフ（surviving route graph）と呼ばれる有向グラフの直径を評価しようという提案がなされている．SR-グラフは，通信網を表したグラフの故障していない点からなり，2点間の通信経路が故障していないとき，その2点間に有向辺をもつ有向グラフとして定義される．本論文では，与えられた整数n，k(n＞k≧3) に対して，k－1以下の任意の故障に対して，SR-グラフの直径が3以下となる両方向，（準）最短かつ無矛盾（consistent）な路線割当てをもつ，点数nで直径がたかだか2logk－1(n)である辺数最小（または辺数最小に近い）グラフGを構成できることを示す．
Institute of Electronics, Information and Communication Engineersの論文
1989-11-20

直径の小さいグラフとその上の耐故障性路線割当ての構成

スポンサーリンク

概要

著者

関連論文

スポンサーリンク