最大クリーク問題の多項式時間的可解性の改良結果

中西 裕陽  富田 悦次  

誌名
電子情報通信学会論文誌 D   Vol.J94-D   No.5   pp.843-851
発行日: 2011/05/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 論文
専門分野: 情報・システム基礎
キーワード: 
NP完全,  最大クリーク,  深さ優先探索,  時間計算量,  最大次数,  

本文: PDF(324.1KB)>>
論文を購入




あらまし: 
典型的なNP完全問題である最大クリーク問題に対して,本論文では次の結果を示す.すなわち,節点数nの一般グラフにおいて,最大次数ΔがΔ ≤ 2.613d lg n (d ≥ 1: 定数)なる条件を満たしているとき,このグラフの最大クリーク問題はO(n1+d)なる多項式時間で可解である.ここで,特に定数d=1としたときにおける時間計算量O(n2)は,節点数nに関してオーダとして最適である.これは,先に発表した結果(信学論(D),vol. J93-D, no.4, pp.417-425, April 2010)の直接的改良であり,先のアルゴリズムに“部分問題の統合による探索領域削減”という手法,解析を新たに開発・導入することにより,探索領域削減を達成し,本結果を得ている.