Algorithms For Solving the Maximum Clique Problem

Article Sidebar

PDF
Published: Mar 30, 2018
Keywords:
Maximum Clique, Combinatorial Optimization, Computer Algorithm

Main Article Content

Chartchai Leenawong*
Department of Mathematics and Computer Science, Faculty of Science, King Mongkut’s Institute of Technology LadKrabang, Bangkok, Thailand.
Rungaree Santawakup
Department of Mathematics and Computer Science, Faculty of Science, King Mongkut’s Institute of Technology LadKrabang, Bangkok, Thailand.

Abstract

 


Given a graph, in a well-known combinatorial optimization problem, the search for a maximum clique is investigated here. A clique of a graph is a set of vertices, any two of which are adjacent. The maximum clique problem asks for a clique having a large vertex (node) set. This research modifies a specific previous algorithm that uses branch and bound as well as pruning strategy by reordering the vertices according to the degrees of vertices. Then the new algorithm and some previous algorithms are implemented on a computer to compare the results of these algorithms on a certain type of graphs, namely, random graphs. In addition, for approximation proposes, an algorithm for solving the minimum vertex color problem is also implemented because of the face that the solution to this problem is an upper bound to the solution of the maximum clique problem.


Keywords: Maximum Clique, Combinatorial Optimization, Computer Algorithm.


Corresponding author: E-mail: klchartc@kmitl.ac.th


 

Article Details

Issue
Vol. 6 No. 2a (2006)
Section
Original Research Articles

Copyright Transfer Statement

 The copyright of this article is transferred to Current Applied Science and Technology journal with effect if and when the article is accepted for publication. The copyright transfer covers the exclusive right to reproduce and distribute the article, including reprints, translations, photographic reproductions, electronic form (offline, online) or any other reproductions of similar nature.

 The author warrants that this contribution is original and that he/she has full power to make this grant. The author signs for and accepts responsibility for releasing this material on behalf of any and all co-authors.

Here is the link for download: Copyright transfer form.pdf

 

 

References

[1] Garey, M.R. and Johnson, D.S. 1979 Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, W.H. Freeman.
[2] Pardalos, P.M. and Xue, J. 1994 The Maximum Clique Problem, Journal of Global Optimization, 4, 301-328.
[3] Carraghan, R. and Pardalos, P.M. 1990 An Exact Algorithm for the Maximum Clique problem, Operation Research Letters, 9, 375-382.
[4] Östergård, P.R.J. 2002 A Fast Algorithm for the Maximum Clique Problem, Discrete Applied Mathematics, 120, 195-205.
[5] Gould, R. 1988 Graph Theory: California, Benjamin/Cummings Publishing.