文献

J-GLOBAL ID：201802276377646571   整理番号：18A0162621

1000000000スケールネットワーク上の三角形禁止問題のためのスケーラブルで適応アルゴリズム【Powered by NICT】

Scalable and Adaptive Algorithms for the Triangle Interdiction Problem on Billion-Scale Networks

著者 (3件)： Kuhnle Alan ,  Crawford Victoria G. ,  Thai My T.
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： ICDM  ページ： 237-246  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 様々なネットワークアプリケーションのクラスター化または推移の関連性に触発されて,三角形禁止問題(TIP),ネットワークの全ての三角形を交差するエッジの最小-サイズの集合を見つけることであることを研究した。このNP困難問題のための既存の近似アルゴリズムは,大規模ネットワークに良くスケールしないまたは悪い解の品質を持っているので,最適に関して,TARLとDART,二つのアルゴリズムを定式化した最悪ケース保証5/2および3であった。さらに,DARTは動的エッジ挿入と除去ネットワークへの下での最悪ケース保証を効率的に保持することができた。著者らの包括的実験的評価では,DARTは2時間以内に三角形の十億を持つネットワーク上で実行することができ,マイクロ秒溶液を動的に更新することができることを示した。Copyright 2018 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： *ネットワーク ,  クラスタ化 ,  CASE ,  *アルゴリズム ,  品質 ,  定式化
準シソーラス用語： マイクロ秒 ,  大規模ネットワーク ,  近似アルゴリズム ,  NP困難問題 ,  ネットワークアプリケーション ,  *適応アルゴリズム , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (5件)： スケール ,  三角形 ,  禁止 ,  問題 ,  適応アルゴリズム