Contraction-based method for computing a lower bound on the clique number of a graph
Assia Gueham, Hacène Aït Haddadène, Anass Nagih · 2019
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.