Dipartimento di Scienze Statistiche

In this paper a new procedure for nding 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 suciently 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.