DocumentCode
3156590
Title
A polynomial-time algorithm for the maximum clique problem
Author
Akbari, Zohreh O.
Author_Institution
Dept. of Math. & Comput. Sci., Friedrich Schiller Univ., Jena, Germany
fYear
2013
fDate
16-20 June 2013
Firstpage
503
Lastpage
507
Abstract
After more than six decades of its introduction, the maximum clique problem, which is one of the most applicable problems in the graph theory, has still no polynomial-time solution. This paper presents a polynomial-time algorithm for this problem, which detects the maximum clique of a given graph through a recursive approach. This polynomial solution to the clique problem, as an NP-complete problem, causes every problem in NP to have a polynomial solution, which leads to the equality of P and NP complexity classes.
Keywords
computational complexity; graph theory; NP complexity class; NP-complete problem; P complexity class; graph theory; maximum clique problem; polynomial solution; polynomial-time algorithm; recursive approach; Approximation algorithms; Approximation methods; NP-complete problem; Optimization; Polynomials; Time complexity; Computational Complexity Theory; Maximum Clique Problem; NP-Complete Problems; P versus NP Problem; Polynomial-Time Algorit hm; Recursive Opti mization;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer and Information Science (ICIS), 2013 IEEE/ACIS 12th International Conference on
Conference_Location
Niigata
Type
conf
DOI
10.1109/ICIS.2013.6607889
Filename
6607889
Link To Document