文献

J-GLOBAL ID：200902243724469142   整理番号：07A1170619

最大クリークを抽出する時間計算量O(2^0.24945n)の多項式領域アルゴリズム

An O(2^0.24945n)-time and Polynomial-space Algorithm for Finding a Maximum Clique

著者 (2件)： 中西裕陽 (電通大 大学院電気通信学研究科) ,  富田悦次 (電通大 大学院電気通信学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 107  号： 258(COMP2007 41-47)  ページ： 33-40  発行年： 2007年10月09日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 無向グラフ中の最大クリークを抽出する問題はNP困難であり,自...

シソーラス用語： *NP困難 ,...
準シソーラス用語： 計算の複雑さ ,...

   続きはJDreamIII（有料）にて  {{ this.onShowAbsJLink("http://jdream3.com/lp/jglobal/index.html?docNo=07A1170619&from=J-GLOBAL&jstjournalNo=S0532B") }}

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

引用文献 (10件)：

• TARJAN, R. E. Findig a maximum independent set. SIAM Journal on Computing. 1977, 6, 537-546
• JIAN, T. An O(2^<0.304n>) algorithm for solving maximum independent set problem. IEEE Transactions on Computing. 1986, 35, 847-851
• ROBSON, J. M. Algorithms for maximum independent sets. Journal on Algorithms. 1986, 7, 425-440
• SHINDO, M. A simple algorithm for finding a maximum clique and its worst-case time complexity. Systems and Conputing in Japan. 1990, 21, 1-13
• BEIGEL, R. Finding maximum independent sets in sparse and general graphs. Proceedings of the Tenth Annual ACM-SIAM Symposium On Discrete Algorithms, 1999. 1999, 856-857

タイトルに関連する用語 (4件)： 最大クリーク ,  時間計算量 ,  多項式 ,  アルゴリズム