- 著者
-
中西 裕陽
富田 悦次
若月 光夫
西野 哲朗
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 研究報告アルゴリズム(AL) (ISSN:09135685)
- 巻号頁・発行日
- vol.2014, no.14, pp.1-8, 2014-06-06
NP 完全である最大クリーク問題に対し,"節点数 n≧1 のグラフにおいて,グラフ中の任意の隣接 2 節点 vi,vj∈V, (vi,vj)∈E が min{deg(vi), deg(vj)}≦3.486d lg n (d ≧0: 定数) を満たすならば,最大クリーク問題は O(n2+max{d,1}) 時間で解決可能である." ことを示す.これは,先に発表した結果 (信学論 (D),vol.J97-D,no.6,June 2014) の定量的改良である.This paper presents a further improved extended result for polynomial-time solvability of the maximum clique problem, that is: for any adjacent pair of vertices p and q where the degree of p is less than or equal to that of q in a graph with n vertices, if the degree of p is less than or equal to 3.486d lg n (d≧0: a constant), then the maximum clique problem is solvable in the polynomial time of O(n2+max{d,1}). This result is obtained by more detailed analysis and the corresponding detailed algorithm.