新k shortest simple pathアルゴリズムによる平均時間計算量削減
スポンサーリンク
概要
- 論文の詳細を見る
著者は方向性グラフ上でのk shortest simple path生成を最悪時間計算量O(km(log n+log k))で実現するk-SPF-plusアルゴリズムを提案した(nは頂点数、mはエッジ数)。本稿では、k-SPF-plusの最悪時間計算量の算出根拠を明確にするとともに、k-SPF-plusの平均時間計算量を解析し、その値がO(km+(m+kn)(log n+log k))であることを示す。この近似平均時間計算量はO(km)であり、Yenのアルゴリズム、Gotthilfのアルゴリズム等の他の既存アルゴリズムの近似平均時間計算量O(kmn)を大幅に縮められることがわかる。
- 2011-03-02
著者
関連論文
- EJBによるレイヤ1VPNカスタマNMSの実装(GMPLS管理,情報通信マネジメント,一般)
- P2MP TEに適用するSteiner Treeアルゴリズムの検討(次世代・新世代ネットワークアーキテクチャ,トラヒック計測・制御,サービス品質,ネットワーク管理,一般)
- 階層分散型NMSを用いたGMPLS網ルーティング方式(セッション4)
- B-7-71 新K Shortest Path生成アルゴリズムによる計算量削減(B-7.情報ネットワーク,一般セッション)
- B-6-54 IPTVに適用するP2MP Tree生成アルゴリズムの検討(B-6.ネットワークシステム,一般セッション)
- B-6-128 マルチパスを利用したセンサートラフィック分散方式の提案(B-6.ネットワークシステム,一般セッション)
- B-14-12 VPN単位の管理を導入したL1-VPN管理システム(B-14. テレコミュニケーションマネジメント,一般セッション)
- GMPLSパス構成/故障管理手法(次世代ネットワークアーキテクチャ,次世代ネットワークのオペレーションアーキテクチャ,トラヒック計測・モデリング・品質,オーバレイネットワーク,一般)
- B-6-37 階層分散型PCEによるマルチキャストTraffic Engineering手法の提案(B-6.ネットワークシステム,一般講演)
- 階層分散型PCEによるマルチキャストツリー生成アルゴリズムの提案
- B-7-72 エンドツーエンドQoSを保証するGMPLS VPN管理法の提案(B-7.情報ネットワーク,一般講演)
- IM2005国際会議報告(設備管理, ネットワーク管理, 及び一般)
- 階層分散型NMSを用いたGMPLS網ルーティング方式(セッション4)
- BS-3-6 高速マルチパス生成を実現するk shortest simple pathアルゴリズム提案と実装評価(BS-3.次世代ICTインフラの実現に向けたネットワーク制御・管理技術,シンポジウムセッション)
- B-7-26 方向性Steinerアルゴリズムの計算量最小化検討(B-7.情報ネットワーク,一般セッション)
- 新k shortest simple pathアルゴリズムによる平均時間計算量削減
- 計算量最小化を実現するk shortest simple pathアルゴリズム提案(トラヒック計測・制御,ポリシー管理,ネットワーク異常検知,信頼性,認証,ID/名前空間,ネットワークセキュリティ,プライバシー,VPN,DDoS及び一般)
- B-14-16 センター集中型サービスに適用するマルチパス方式の検討(B-14. 情報通信マネジメント,一般セッション)
- 新マルチパス生成アルゴリズムを利用したVoD配信ネットワークの実現(IPv6ネットワーク,フォトニックネットワーク,新世代・次世代ネットワーク及び一般)
- マルチキャストパスコストとネットワークリソースを最適化するSteinerアルゴリズムの検討(ネットワーク管理,ネットワーク品質,一般)
- マルチキャストパスコストとネットワークリソースを最適化する Steiner アルゴリズムの検討
- P2MP-TEに適用する新Steiner treeアルゴリズムの提案(サービス管理,運用管理技術,セキュリティ管理,及び一般)
- Steiner treeの省エネルギールーティングへの適用検討(ホームネットワーク,ユビキタスネットワーク,クラウドコンピューティング,コンテキストアウェア,位置情報サービス,e-コマース及び一般)
- D-1-2 Steiner treeアルゴリズムBBMCの平均時間計算量解析(D-1.コンピュテーション)
- P2MP-TEに適用する新 Steiner tree アルゴリズムの提案