点数の少ない多重サイクルグラフ上の耐故障性路線割当
スポンサーリンク
概要
- 論文の詳細を見る
計算機網（一般に通信網）の構成問題は，計算機を点，通信線を辺に対応させたグラフとその上の路線（route）をいかに構成するかと言う問題である．通信網において（k－1）個以内の要素が故障したとき，故障した要素を含まない高々d個の路線を接続すれば，いかなる2点間の通信も可能であるならば，この路線割当（ruting）は（d，k－1）-耐性であると言う．従来，3m≦n≦6m＋1，k＝2m＋1，m≧2を満たすn，kを除く全ての整数n，k（但し，n＞k≧2）に対し，辺数最小のn点から成るk-点連結グラフ（（n，k）-多重サイクルグラフ）とその上の（3，k－1） 耐性の両方向性最短路線割当が構成可能な事が分かっていたが，本論文は，除外されていた上記の場合に対しても同じ結果が得られる事を示す．これにより，全ての（n，k）-多重サイクルグラフに対して（3，k－1）-耐性の両方向性最短路線割当が構成可能かと言う設問に応える肯定的解を完整した事になる．
- Institute of Electronics, Information and Communication Engineersの論文
- 1991-03-00
著者
関連論文
- ソート集合のある分割に対する並列アルゴリズムについて
- マルチメディアを用いた導入教育
- 命令再構成型VLIWプロセッサV++における2つの再構成機能の評価
- バリア同期のためのタスクスケジューリングアルゴリズムとその性能評価
- 命令再構成型VLIWプロセッサV++における適応型再構成戦略
- 重複可能なバリア型同期のための最適バリアスケジューリング
- 概念制約式を用いたプログラミングを可能にするコンパイル手法
- バリアを唯一の同期手段とした場合のタスクスケジューリング
- 自己組織系集団による通信の進化の試み
- ランギーII:仮想的生物による通信の進化
- 複数種の生物集団の共存する人工生命環境の設計
- 概念制約式を用いたプログラミングとプログラム合成
- 星状多角形内の同期式自律分散ロボットの一点集合問題
- 2連結グラフに対するATM網に適した最適な耐故障性ルーティング
- 点集合の強凸-包含を求めるアルゴリズム
- スーパーキューブの耐故障性について
- 2辺連結グラフの4分割について
- グラフのあるk-分割問題に対する効率的なアルゴリズムについて
- 重みつきグラフのk分割問題について
- 3個の空位をもつN×M-平面自動倉庫(N,M≧3)の最小歩数関数
- 異なる半径の数を限定した円集合の凸包を求める最適並列アルゴリズム
- 誤差耐性のある強凸包構成問題に対する並列解法
- 拡張超立方体グラフに対する耐故障性路線割当と直径罹障度
- 円集合の凸包を求める効率の良い並列アルゴリズム
- コンパイラ教育支援システムにおける属性文法に基づく意味解析系提示ツールの作成
- アルゴリズムの可視化に基づくコンパイラ教育支援システム
- k-辺連結有向(無向)グラフに対する高信頼性路線割当の存在条件と計算量
- 通信網に対する高信頼性最適路線割当ての存在条件と計算量の改善
- 3個の空位を持つN×M-平面自動倉庫の最小歩数関数
- 連結グラフの(L,κ)-辺分割線形時間アルゴリズムとκ-辺連結グラフに対する高信頼性路線割当
- 3連結グラフにおける3-独立木構成アルゴリズムと2点間の内点独立路を求めるアルゴリズム
- 非阻塞グラフに関する一考察
- 故障発生時の連結性判定問題を解く分散アルゴリズムについて
- 点数の少ない多重サイクルグラフ上の耐故障性路線割当
- 多重サイクルグラフ上の高信頼性路線割当の構成
- 故障耐性の高い路線割当をもつ通信網の構成問題
- (k+1)-点連結,および(k+1)-辺連結グラフに対する高信頼性通信網路線割当について
- 直径の小さいグラフとその上の耐故障性路線割当ての構成
- 有向,無効グラフに対する最適なt-spannerの構成について
- 一般化された埋込み方式のもとでのグラフの埋込み面積の上・下界
- 一般のグラフの埋込み面積のMax-Min下界
- 故障耐性の高い路線割当をもつ通信網の構成問題
- (k+1)-点連結,および(k+1)-辺連結グラフに対する高信頼性通信網路線割当について
- 多重サイクルグラフ上の高信頼性路線割当ての構成
- 一般化された埋込み方式のもとでのグラフの埋込み面積の上・下界
- 故障が存在する計算機網に対する連結性判定分散アルゴリズム
- 直径の小さいグラフとその上の耐故障性路線割当ての構成
- 一般のグラフの埋込み面積のMax-Min下界
- 点数の少ない多重サイクルグラフ上の耐故障性路線割当