@techreport{oai:ipsj.ixsq.nii.ac.jp:00101701, author = {中西, 裕陽 and 富田, 悦次 and 若月, 光夫 and 西野, 哲朗 and Hiroaki, Nakanishi and Etsuji, Tomita and Mitsuo, Wakatsuki and Tetsuro, Nishino}, issue = {14}, month = {Jun}, note = {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.}, title = {最大クリーク問題の多項式時間的可解性の拡張の更なる改良}, year = {2014} }