CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Exact Polynomial-time Algorithm for the Clique Problem and P = NP for Clique Problem

by Kanak Chandra Bora, Bichitra Kalita
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 73 - Number 8
Year of Publication: 2013
Authors: Kanak Chandra Bora, Bichitra Kalita
10.5120/12761-9472

Kanak Chandra Bora, Bichitra Kalita . Exact Polynomial-time Algorithm for the Clique Problem and P = NP for Clique Problem. International Journal of Computer Applications. 73, 8 ( July 2013), 19-23. DOI=10.5120/12761-9472

@article{ 10.5120/12761-9472,
author = { Kanak Chandra Bora, Bichitra Kalita },
title = { Exact Polynomial-time Algorithm for the Clique Problem and P = NP for Clique Problem },
journal = { International Journal of Computer Applications },
issue_date = { July 2013 },
volume = { 73 },
number = { 8 },
month = { July },
year = { 2013 },
issn = { 0975-8887 },
pages = { 19-23 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume73/number8/12761-9472/ },
doi = { 10.5120/12761-9472 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:39:31.864156+05:30
%A Kanak Chandra Bora
%A Bichitra Kalita
%T Exact Polynomial-time Algorithm for the Clique Problem and P = NP for Clique Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 73
%N 8
%P 19-23
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In this paper, the Minimum Nil Sweeper Algorithm, applicable to Clique problem has been considered. It has been found that the Minimum Nil Sweeper Algorithm is not applicable to Clique problem for all undirected graphs which was previously claimed. A new algorithm has been developed to study the all clique problems for arbitrary undirected graph and its complexity is analysed. An experimental result is cited. Finally, the P = NP has been proved for Clique problem. A theorem related to intersection graph is developed.

References
  1. Richard E. Neapolitan and Kumarss Naimipour, "Foundations of Algorithms using C++ Pseudcode", 3rd ed, Jones and Bartlett Publishers, 2003, ch. 9.
  2. Michael Sipser, "Introduction to the Theory of Computation", 2nd ed. , International Edition, Thomson Course Technology, p 270, definition 7. 19 and theorem 7. 20, 2006.
  3. Stephen A. Cook, "The complexity of theorem-proving procedures", Proceedings of Third Annual ACM Symposium on Theory of Computing, pages 151-158, 1971.
  4. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, "Introduction to Algorithms", 2nd ed. , MIT Press and McGraw-Hill, 2001, ch. 22 and ch. 34.
  5. Stephen A. Cook, "The P versus NP problem", Manuscript prepared for the Clay Mathematics Institute for the Millennium Prize Problems, 2000.
  6. Richard M. Karp, "Reducibility among combinational problems", In R. E. Miller and J. W. Thatcher (editors): Complexity of Computer Computations, pages 85-103. New York: Plenum Press, 1972.
  7. Alon, N. ; Boppana, R. (1987), "The monotone circuit complexity of Boolean functions", Combinatorica 7(1): 1-22, doi:10. 1007/BF02579196.
  8. K. Makino and T. Uno, "New algorithms for enumerating all maximal cliques," In Proc. of the 9th Scandinavian Workshop on Algorithm Theory (SWAT 2004), pp. 260-272. Springer-Verlag, 2004
  9. E. Tomita, A. Tanaka, and H. Takahashi, "The worst-case time complexity for generating all maximal cliques and computational experiments," Theoretical Computer Science, vol. 363, pp. 28-42, 2006.
  10. Takeaki UNO, "Implementation issues of clique enumeration algorithm", Special issue: Theoretical computer science and discrete mathematics, Progress in Informatics, No. 9, pp. 25-30, (2012).
  11. Zohreh O. Akbari, "A Deterministic Polynomial-time Algorithm for the Clique Problem and the Equality of P and NP Complexity Classes", World Academy of Science, Engineering and Technology 45 2008.
  12. Rongdeep Pathok, Bichitra Kalita, "Properties of Some Euler Graphs Constructed from Euler Diagram", Int. Journal of Applied Sciences and Engineering Research, Vol. I, No. 2, 2012, pp. 232-237.
  13. C. Bron, J. Kerbosch, Algorithm 457, finding all cliques of an undirected graph, Comm. ACM 16 (1973) 575-577.
  14. J. W. Moon, L. Moser, On cliques in graphs, Israel J. Math. 3 (1965) 23-28.
  15. S. Tsukiyama, M. Ide, H. Ariyoshi, I. Shirakawa, A new algorithm for generating all the maximal independent sets, SIAM J. Comput. 6 (1977) 505-517.
  16. N. Chiba, T. Nishizeki, Arboricity and subgraph listing algorithms, SIAJ J. Comput. 14 (1985) 210 – 223.
Index Terms

Computer Science
Information Sciences

Keywords

Exact Polynomial-time Algorithm Clique Euler-diagram Complexity. P=NP

Powered by PhDFocusTM