(k+1)-点連結,および(k+1)-辺連結グラフに対する高信頼性通信網路線割当について

スポンサーリンク

概要

• 論文の詳細を見る

• 通信網や計算機網における情報伝達の信頼性をいかに経済的に効率よく高めるかは重要な問題である．通常，通信網（計算機網）は局（計算機）を点，通信回線を辺としたグラフで表され，任意の二点間の通信はグラフの通路を用いて行われる．通信網の二点間の通信経路を決定することを路線割当（routing）と呼ぶが，路線割当が前もって計算されている通信網の信頼性の尺度として，通信網を表すグラフとその路線割当および，故障点と故障辺によって定義されるSR-グラフ（surviving route graph）と呼ばれるグラフの直径を評価しようという提案がなされている．SR-グラフは，通信網を表したグラフの故障していない点からなり，二点間の通信経路が故障していないとき，その二点間に有向辺をもつ有向グラフとして定義される．本論文では，(k＋1)-点連結グラフと(k＋1)- 辺連結グラフにおける路線割当に対するSR-グラフの直径を議論する．まず，文献(2)で与えられた(k＋1)-点連結グラフにおける路線割当に対するSR-グラフの直径の上界を改善する．ここで得られた結果は文献(2)の結果の改善であると同時にそれを含む一般化になっている．また，その路線割当に対するSR-グラフの直径の下界を導出する．更に，(k＋1)-辺連結グラフに対する路線割当を与え，故障が辺だけからなるならばSR-グラフの直径が定数となることを示す．

• Institute of Electronics, Information and Communication Engineersの論文
• 1986-12-20

著者

• 羅 予頻

  清華大学

関連論文

• 2連結グラフに対するATM網に適した最適な耐故障性ルーティング
• 点数の少ない多重サイクルグラフ上の耐故障性路線割当
• 多重サイクルグラフ上の高信頼性路線割当の構成
• 故障耐性の高い路線割当をもつ通信網の構成問題
• (k+1)-点連結,および(k+1)-辺連結グラフに対する高信頼性通信網路線割当について
• 故障耐性の高い路線割当をもつ通信網の構成問題
• (k+1)-点連結,および(k+1)-辺連結グラフに対する高信頼性通信網路線割当について
• 多重サイクルグラフ上の高信頼性路線割当ての構成
• 点数の少ない多重サイクルグラフ上の耐故障性路線割当

スポンサーリンク