An Improved Extended Result on Polynomial-Time Solvability of the Maximum Clique Problem

Hiroaki NAKANISHI  Etsuji TOMITA  Mitsuo WAKATSUKI  Tetsuro NISHINO  

Publication
D - Abstracts of IEICE TRANSACTIONS on Information and Systems (Japanese Edition)   Vol.J97-D   No.6   pp.1106-1121
Publication Date: 2014/06/01
Online ISSN: 1881-0225
Type of Manuscript: PAPER
Category: 
Keyword: 
NP-complete,  maximum clique,  depth-first search,  time-complexity,  degree of a vertex,  

Full Text(in Japanese): PDF(563.2KB)
>>Buy this Article


Summary: 
This paper presents an improved extended result for polynomial-time solvability of the maximum clique problem, that is: for a general graph with n vertices, if the maximum degree of a graph is less than or equal to 3.177d lg n (d ≥ 0: a constant), then the maximum clique problem is solvable in the polynomial time of O(n1+d). This result is obtained by more detailed analysis and the corresponding detailed algorithm.