For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
An Improved Extended Result on Polynomial-Time Solvability of the Maximum Clique Problem
Hiroaki NAKANISHI Etsuji TOMITA Mitsuo WAKATSUKI Tetsuro NISHINO
D - Abstracts of IEICE TRANSACTIONS on Information and Systems (Japanese Edition)
Publication Date: 2014/06/01
Online ISSN: 1881-0225
Type of Manuscript: PAPER
NP-complete, maximum clique, depth-first search, time-complexity, degree of a vertex,
Full Text(in Japanese): PDF(563.2KB)
>>Buy this Article
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.