A simple and efficient heuristic algorithm for maximum clique problem

A clique is a sub graph in which all pairs of vertices are mutually adjacent. A maximum clique is a maximum collection of objects which are mutually related in some specified criterion. This paper proposes an efficient heuristic approach for finding maximum clique using minimal independent set in a graph. At each recursive step, the algorithm finds minimal independent vertices for further expansion to get adjacent list, reason is that at the depth, the maximum clique most likely would include either of the vertices of minimal independent set. Further a pruning strategy is used to abort smaller size of clique to be explored.