最大クリーク問題の多項式時間的可解性の拡張

中西 裕陽  富田 悦次  若月 光夫  西野 哲朗  

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

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




あらまし: 
典型的なNP完全問題である最大クリーク問題に対し,本論文では,次の結果を示す:“節点数nの一般グラフにおいて,Gの最大次数ΔがΔ ≤ 2.994d lg nd 0: 定数)なる条件を満たすとき,このグラフの最大クリーク問題はO(n1+d)なる多項式時間で可解である.”これに先立ち,最大次数ΔがΔ 2.773d lg nd 0: 定数)である場合に同様の結果を得ている(信学論(D),vol. J94-D, no. 12, pp. 2037-2046)が,本論文では,前結果における状況をより詳細に解析した上で,最大時間計算量が大きくなる場合に対して,更に詳細な場合分けを伴ったアルゴリズムと時間計算量解析を導入することにより,本結果を得ている.