Groupe d’études et de recherche en analyse des décisions

G-2012-80

A Repeated Sequential Elimination Algorithm for Finding an Upper Bound on the Clique Number

, et

In this paper a new procedure for finding an upper bound on the clique number of a given graph is described. Gendron, Hertz and St-Louis (2008) proposed a sequential elimination algorithm which, given any method that computes an upper bound on the clique number, improves upon that bound by iteratively reducing the graph. The idea of the new algorithm is to apply the sequential elimination algorithm to the given graph and then apply it again to some subgraphs in order to further improve the obtained bound. A preliminary set of computational results shows that if the new algorithm is associated with a simple but sufficiently accurate method for computing an upper bound on the clique number it can substantially improve the bounds obtained with the Gendron, Hertz and St-Louis algorithm within reasonable execution times.

, 13 pages