Contraction-based method for computing a lower bound on the clique number of a graph

摘要

This paper proposes a new method to determine the clique of maximum cardinality in a graph. More precisely, we propose a contraction-based approach, which uses the orientation algorithm and the labeling order scheme of vertices. This method allows to effeciently compute both upper and lower bounds of the clique number. The experimental results on instances of the library DIMACS are validated against our method.