Algorithms For Solving the Maximum Clique Problem
Article Sidebar
Main Article Content
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
Copyright Agreement Statement
The corresponding author has to submit Copyright Agreement form after the article is accepted for publication in order to warrant 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.
The author(s) grant Current Applied Science and Technology a non-exclusive, irrevocable, royalty-free license to publish, reproduce, distribute, and archive the article in print and electronic form with effect if and when the article is accepted for publication. In the event that the article is withdrawn prior to acceptance or is declined, this agreement shall have no effect, and no party shall be bound by it.
The author(s) retain copyright of this article, including but not limited to the right to reproduce and distribute the article, to include it in a thesis or book, and to post it on an institutional or personal repository, provided that the original publication in Current Applied Science and Technology is properly cited.
References
[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.
