講演抄録/キーワード |
講演名 |
2010-12-03 14:30
最大クリーク問題の多項式時間的可解性の改良結果 ○中西裕陽(電通大)・富田悦次(電通大/中大) COMP2010-43 |
抄録 |
(和) |
典型的なNP完全問題である最大クリーク問題に対して,本論文では次の結果を示す.
即ち,節点数nの一般グラフにおいて,
最大次数ΔがΔ≦2.613dlg n (d ≧ 1: 定数)なる条件を満たしている時,このグラフの最大クリーク問題はO(n^{1+d})なる多項式時間で可解である.
ここで,特に定数d=1とした時における時間計算量O(n^{2})は,節点数nに関してオーダとして最適である.
これは,先に発表した結果(信学論 D, vol.J93-D, no.4, pp.417--425)の直接的改良であり,
先のアルゴリズムに``部分問題の統合による探索領域削減"という手法,
解析を新たに開発・導入
することにより,探索領域削減を達成し,本結果を得ている. |
(英) |
This report presents an improved result for polynomial-time solvability of the maximum clique problem which is a typical NP complete problem.
That is:
for a graph with n vertices, if the maximum degree Δ is less than or equal to 2.613dlg n (d ≧ 1: a constant), then
the maximum clique problem is solvable in the polynomial
time of O(n^{1+d}).
In particular, in case $d=1$, the time complexity of O(n^{2}) is optimal with respect to the number n of vertices .
This is a direct improvement of our preceding result in Trans. IEICE, vol.J93-D, no.4, pp.417--425.
Such an improvement has been achieved by introducing a new technique to
successfully reduce the search space. |
キーワード |
(和) |
NP完全 / 最大クリーク / 深さ優先探索 / 時間計算量 / 最大次数 / / / |
(英) |
NP-Complete / Maximum Clique / Depth-First Search / Time-Complexity / Maximum Degree / / / |
文献情報 |
信学技報, vol. 110, no. 325, COMP2010-43, pp. 29-36, 2010年12月. |
資料番号 |
COMP2010-43 |
発行日 |
2010-11-26 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2010-43 |