| Article ID: | iaor20084070 |
| Country: | United Kingdom |
| Volume: | 17 |
| Issue: | 5 |
| Start Page Number: | 437 |
| End Page Number: | 445 |
| Publication Date: | Jul 1990 |
| Journal: | Computers and Operations Research |
| Authors: | Werra D. de, Friden C., Hertz A. |
| Keywords: | heuristics: tabu search, sets |
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 or 500 nodes (with edge density 0.5) can be handled by this approach.