Tabaris: An exact algorithm based on Tabu Search for finding a maximum independent set in a graph

A technique for finding in a graph an independent set with maximum cardinality is presented. It consists of an implicit enumeration procedure; the procedure uses at various stages bounds on the independence number of a subgraph. These are obtained by applying an adaptation of Tabu Search. Computational results are given which show that with Tabu Search a competitive algorithm is obtained; the case of randomly generated graphs having up to 450 to 500 nodes (with edge density 0.5) can be handled by this approach.