文献

J-GLOBAL ID：201002256209440803   整理番号：10A0662457

ネットワーク脆弱性評価のための新しい最適化法の近似

On Approximation of New Optimization Methods for Assessing Network Vulnerability

著者 (5件)： DINH Thang N. (Univ. Florida, FL) ,  XUAN Ying (Univ. Florida, FL) ,  THAI My T. (Univ. Florida, FL) ,  PARK E. K. (Univ. Missouri at Kansas City, MO) ,  ZNATI Taieb (Univ. Pittsburgh, PA)
資料名： Proceedings. IEEE INFOCOM  (Proceedings. IEEE INFOCOM)
巻： 2010 Vol.3  ページ： 2678-2686  発行年： 2010年 
JST資料番号： E0920A  ISSN： 0743-166X  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 結合性はネットワーク性能に影響を与え,脆弱性評価の基盤となる。脆弱性研究においては,ネットワークをグラフとして抽象化し,その特性を求める。これら研究はグラフ全体の特性に注目をする方式と,局所特定に注目する方式とに分けられるが,いずれも脆弱性を正確に表現できていない。本論文では,対象ネットワークを有向グラフとしてモデル化し,定義されたネットワーク破壊をもたらす最小のノード/エッジ集合を直接求めることを行った。この評価をグラフ理論的な最適化問題に変換し,この最少集合を求めた。この問題は有向グラフにおいてNP完全であることを示した。さらには,単一コストからなる無向グラフにおいてもNP完全であることを示した。2つの近似アルゴリズムを提示し,そのバウンドも証明した。提案したヒューリスティックスアルゴリズムの高性能を,既存アルゴリズムと比較して示した。

シソーラス用語： *通信網 ,  *グラフ理論 ,  信頼性解析 ,  最適化手法 ,  近似法 ,  連結性 ,  有向グラフ ,  NP完全問題 ,  発見的方法
準シソーラス用語： ヒューリスティクス ,  近似解法 ,  結合性 ,  脆弱性

分類 (2件)： 通信網  (ND07030A) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (3件)： 脆弱性評価 ,  最適化 ,  近似