Algorithms For Solving the Maximum Clique Problem

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