文献

J-GLOBAL ID：201102255866830000   整理番号：11A0179579

計算量最小化を実現するk shortest simple pathアルゴリズム提案

A proposal of k shortest simple path algorithm to minimize computational complexity

著者 (1件)： 松浦洋 (NTT サービスインテグレーション基盤研)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 110  号： 341(IN2010 97-117)  ページ： 57-62  発行年： 2010年12月09日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： k shortest pathアルゴリズムはネットワーク上での代替経路生成,複数経路を利用することによる負荷分散等への適用が期待される。方向性グラフ上でループレスなk shortest pathを生成するk shortest simple path生成アルゴリズムは,50年間の長きに渡り研究されているが,現状O(knm)の計算量が最小である(nはノード数,mはリンク数)。本稿では,この計算量をO(km(log n+log k))に短縮するアルゴリズム(k-SPF)を提案するとともに,k-SPFアルゴリズムと既存のYenアルゴリズムを実装し,その処理時間を比較する。(著者抄録)

シソーラス用語： *計算機網 ,  高速アルゴリズム ,  経路 ,  *経路選定 ,  計算量 ,  ルータ【通信】 ,  データ構造 ,  加工時間 ,  有向グラフ ,  *通信操作
準シソーラス用語： k shortest simple path ,  多経路 ,  エッジルータ ,  処理時間 ,  経路候補数 ,  方向性グラフ

分類 (1件)： 計算機網  (JC03000K)

引用文献 (9件)：

• ASH, J. Path Computation Element (PCE) Communication Protocol Generic Requirements. RFC 4657. 2006
• DZIDA, M. Optimization of the Shortest-Path Routing with Equal-Cost Multi-Path Load Balancing. Transparent Optical Networks. 2006, 3, 9-12
• FORTZ, B. Internet Traffic Engineering by Optimizing OSPF Weights. IEEE INFOCOM, March 2000. 2000, 2, 519-528
• SUURBALLE, J. W. Disjointed paths in a network. Networks. 1974, 4, 125-145
• YEN, J. Y. Finding the k shortest Loopless Paths in a Network. Management Science. 1971, 17, 712-716

タイトルに関連する用語 (4件)： 計算量 ,  最小化 ,  アルゴリズム ,  提案