文献

J-GLOBAL ID：201302262406927341   整理番号：13A1793852

計算機実験を用いた最大クリークを見つけるための簡潔でより高速な分岐限定法アルゴリズム

A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique with Computational Experiments

著者 (9件)： TOMITA Etsuji (Advanced Algorithms Res. Lab., The Univ. of Electro-Communications) ,  TOMITA Etsuji (JST ERATO Minato Discrete Structure Manipulation System Project) ,  TOMITA Etsuji (Tokyo Inst. of Technol.) ,  SUTANI Yoichi (Advanced Algorithms Res. Lab., The Univ. of Electro-Communications) ,  SUTANI Yoichi (Sony Corp.) ,  HIGASHI Takanori (Advanced Algorithms Res. Lab., The Univ. of Electro-Communications) ,  HIGASHI Takanori (Japan Systems Co., Ltd.) ,  WAKATSUKI Mitsuo (Advanced Algorithms Res. Lab., The Univ. of Electro-Communications) ,  WAKATSUKI Mitsuo (Graduate School of Informatics and Engineering, The Univ. of Electro-Communications)
資料名： IEICE Transactions on Information and Systems (Institute of Electronics, Information and Communication Engineers)  (IEICE Transactions on Information and Systems (Institute of Electronics, Information and Communication Engineers))
巻： E96-D  号： 6  ページ： 1286-1298 (J-STAGE)  発行年： 2013年 
JST資料番号： L1371A  ISSN： 0916-8532  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 多くの問題は最大クリーク問題として定式化できる。従って,現実的に最大クリークを非常に高速に見つけることができるアルゴリズムを開発することは大変重要である。以前,多数のグラフに対して最高速の最大クリーク発見アルゴリズムとして示された,分岐限定法アルゴリズムMCR(J. Global Optim...,37,pp.95-111,2007)の実行時間を著しく改善する,新しい近似彩色と他の関連技術を提案した。MCRにそれらの新しい技術を導入することにより得られたこのアルゴリズムを,MCSと名付けた。MCSが,低いオーバーヘッドで完全に効率的に,探索空間の低減に成功したことを明らかにした。広範囲な計算機実験により,MCRおよび他の既存アルゴリズムを凌駕するMCSの優位性を確認した。いくつかのグラフに対して,他のアルゴリズムより1桁高速であった。特に,MCSは任意の特定タイプのグラフ用に設計されていないにもかかわらず,非常に高密度の難解なグラフと大規模およびスパースグラフに関して,MCRより高速であった。いくつかの極めて高密度のランダムグラフに対して,100000以上の因子により,MCSはMCRより高速にできた。本稿では,全体の貢献と同様に,MCSにおける各々の新技術の有効性について,詳細に説明した。(翻訳著者抄録)

シソーラス用語： *計算機シミュレーション ,  *最大化問題 ,  クリーク ,  分枝限定法 ,  グラフ ,  彩色問題 ,  空間 ,  高速アルゴリズム
準シソーラス用語： グラフ彩色 ,  *計算機実験 ,  *最大クリーク問題 ,  探索空間 ,  分岐限定法

分類 (1件)： 人工知能  (JE08000Z)

引用文献 (53件)：

• AKUTSU, T. Dynamic programming and clique based approaches for protein threading with profiles and constraint. IEICE Trans. Fundamentals. 2006, 89, 5, 1215-1222
• BAHADUR, D. K. C. Point matching under non-unitform distortions and protein side chain packing based on efficient maximum clique algorithms. Genome Inform. 2005, 13, 143-152
• BAHADUR, D. K. C. Protein side-chain packing problem : A maximum edge-weight clique algoritmic approach. J. Bioinform. and Comput. Biol. 2005, 13, 103-126
• BAHADUR, D. K. C. Protein threading with profiles and distance constraints using clique based algorithms. J. Bioinform. and Comput. Biol. 2006, 14, 19-42
• BALAS, E. Polyhedral methods for the maximum clique problem. DLMACS Series in Discrete Mathematics and Theoretical Computer Science. 1996, 26, 11-28

タイトルに関連する用語 (4件)： 計算機実験 ,  最大クリーク ,  分岐限定法 ,  アルゴリズム