講演抄録/キーワード |
講演名 |
2007-10-16 15:30
最大クリークを抽出する時間計算量O(2^0.24945n)の多項式領域アルゴリズム ○中西裕陽・富田悦次(電通大) COMP2007-46 |
抄録 |
(和) |
無向グラフ中の最大クリークを抽出する問題はNP困難であり, 自明な計算量が
O(P(n)2^n)(P(n)は節点数nの多項式)という困難な問題であって,
その計算量を改善する多くの試みがなされている.
本稿は単純な多項式領域最大クリーク抽出アルゴリズムMAXCLIQUEを提示し,
その最大時間計算量がO(2^0.24945n)となることを示すものである. |
(英) |
The maximum clique problem is an NP-hard problem, and is difficult
to solve efficiently. The trivial upper bound of its time complexity
is O(P(n)2^n), where P(n) is a polynomial of n, the number of
vertices. Several improvements have been done for this upper bound.
In this note, we present a simple polynomial-space algorithm MAXCLIQUE,
and we prove that its time complexity is O(2^0.24945n). |
キーワード |
(和) |
NP困難 / 最大クリーク / 最大独立節点集合 / 時間計算量 / 領域計算量 / / / |
(英) |
NP-hard / Maximum clique / Maximum independent set / Time complexity / Space complexity / / / |
文献情報 |
信学技報, vol. 107, no. 258, COMP2007-46, pp. 33-40, 2007年10月. |
資料番号 |
COMP2007-46 |
発行日 |
2007-10-09 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2007-46 |