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

• Item type: SIG Technical Reports(1)
• 公開日: 2007-11-30
• タイトル: 最大クリークを抽出するO(2^0.19669n)-時間の多項式領域アルゴリズム
• タイトル / 言語: en
• タイトル: An O(2^0.19669n)-time and Polynomial-space Algorithm for Finding a Maximum Clique
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 電気通信大学大学院 電気通信学研究科 情報通信工学専攻
• 著者所属: 電気通信大学大学院 電気通信学研究科 情報通信工学専攻
• 著者所属(英): en
• 著者所属(英): Department of Information and Communication Engineering, Graduate School of Electro-Communications, The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Department of Information and Communication Engineering, Graduate School of Electro-Communications, The University of Electro-Communications
• 著者名: 中西, 裕陽; 富田, 悦次
• 著者名(英): Hiroaki, Nakanishi; Etsuji, Tomita
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 節点数 n のグラフの最大クリーク抽出問題に対する多項式領域アルゴリズムの時間計算量は，Tarjan-Trojanowsky(1977)のO(2^0.333n)から Fomin ら(2006)のO(2^0.288n)に至るまで，この間約 30 年かけての着実な改良が進められてきた．本稿では，既に発表しているShindo-Tomita(1990)のアルゴリズムを基にして．これを更に顕著に改良したO(2^0.19669n)-時間計算量の解析結果を与える．これは，極大クリーク全列挙のための Tomita ら(2006)の最適時間計算量O(3^n/3)=(2^0.528n)に対する明らかな改良となっている．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Steady improvements have been made for the time complexity for finding a maximum clique in an n-vertex graph in polynomial-space from O(0.20333n) by Tarjan-Trojanowsky(1977) to O(20288-) by Fomin et a/.(2006) in these around 30 years. We remarkably improve this complexity to have O(0.19669n)-time based on an algorithm by Shindo-Tomita(1990). This is an obvious improvement of the optimal time complexity of O(3n/3) = (20.528n) for generating all maximal cliques of Tomita et a/.(2006).
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2007, 号 119(2007-AL-115), p. 17-24, 発行日 2007-11-30
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会