講演抄録/キーワード |
講演名 |
2011-04-22 13:55
最大クリーク問題の多項式時間的可解性の更なる改良結果 ○中西裕陽(電通大)・富田悦次(電通大/中大)・若月光夫・西野哲朗(電通大) COMP2011-6 |
抄録 |
(和) |
NP完全である最大クリーク問題に対して,本稿では,``節点数nの一般グラフにおいて,最大次数ΔがΔ ≦ 2.773dlg n (d ≧ 0: 定数)なる条件を満たしているとき,このグラフの最大クリーク問題はO(n^{1+d})なる多項式時間で可解である." ことを示す.これは,先の発表結果(信学技報, COMP2010-43, pp.29--36)の改良であり,最大次数の上限に関する定数を一層増大させて,この定数2.773を得ている. 更に,前発表ではd ≧ 1であった条件をd ≧ 0へと拡張し,dが1よりも小さくて疎なグラフに対しては,時間計算量をO(n^2)よりも小とした.これは,前発表ではグラフを隣接行列で表現することを前提としていたのに対して,本稿では隣接リスト表現を用いることにより実現している.これにより,``最大次数Δが定数である一般グラフにおいて,この最大クリーク問題はO(n)時間で可解である." との結果も得た. |
(英) |
This report presents a further improved result for polynomial-time solvability of the maximum clique problem, that is: for a graph with n vertices, if the maximum degree Δ is less than or equal to 2.773dlg n (d ≧ 0: a constant), then the maximum clique problem is solvable in the polynomial time of O(n^{1+d}). This is an improvement of our preceding result in Tech. Rep. IEICE, COMP2010-43, pp.29--36. The present result is established for a graph represented by an adjacency list. As a result, we show that the maximum clique problem is solvable in O(n)-time if the maximum degree of a graph is a constant. |
キーワード |
(和) |
NP完全 / 最大クリーク / 深さ優先探索 / 時間計算量 / 最大次数 / / / |
(英) |
NP-Complete / Maximum Clique / Depth-First Search / Time-Complexity / Maximum Degree / / / |
文献情報 |
信学技報, vol. 111, no. 20, COMP2011-6, pp. 41-48, 2011年4月. |
資料番号 |
COMP2011-6 |
発行日 |
2011-04-15 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2011-6 |