講演抄録/キーワード |
講演名 |
2007-06-29 09:00
最大クリークを抽出する単純なアルゴリズムの最大次数4のグラフにおける計算量 ○中西裕陽・富田悦次(電通大) COMP2007-18 |
抄録 |
(和) |
無向グラフ中の最大クリークを抽出する問題はNP困難であり, 自明な計算量が
O(P(n)2^n)(P(n)は節点数nの多項式)という困難な問題であって,
その計算量を改善する多くの試みがなされている.
ここでは極大クリーク全列挙アルゴリズムCLIQUESを基にして,
これに分枝限定処理を導入した単純な最大クリーク抽出アルゴリズムを提示する.
最終的な目的はこのアルゴリズムを用いて一般グラフに対する最大クリーク抽出
の計算量上界を改善することであるが, 本稿ではその基礎的な段階として,
最大次数4以下という非常に単純なグラフを扱い, これらにおいては上界が
O(n^3)となることを示す. |
(英) |
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 branch-and-bound algorithm for
the maximum clique problem. It is based on our preceeding algorithm
CLIQUES, which is designed for generating all maximal cliques.
We aim to prove that our algorithm improves the upper bound
for finding a maximum
clique in a general graph, and we show here that it has
O(n^3) upper bound in a graph with maximum degree 4,
as a basis of the analysis for a general case. |
キーワード |
(和) |
NP困難 / 最大クリーク / 最大独立節点集合 / 時間計算量 / / / / |
(英) |
NP-hard / Maximum clique / Maiximum independent set / Time complexity / / / / |
文献情報 |
信学技報, vol. 107, no. 127, COMP2007-18, pp. 1-7, 2007年6月. |
資料番号 |
COMP2007-18 |
発行日 |
2007-06-22 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2007-18 |