| Article ID: | iaor19961286 |
| Country: | United States |
| Volume: | 42 |
| Issue: | 5 |
| Start Page Number: | 860 |
| End Page Number: | 878 |
| Publication Date: | Sep 1994 |
| Journal: | Operations Research |
| Authors: | Feo Thomas A., Resende Mauricio G.C., Smith Stuart H. |
| Keywords: | graphs, heuristics |
An efficient randomized heuristic for a maximum independent set is presented. The procedure is tested on randomly generated graphs having from 400 to 3,500 vertices and edge probabilities from 0.2 to 0.9. The heuristic can be implemented trivially in parallel and is tested on a MIMD computer with 1,2,4 and 8 processors. Computational results indicate that the heuristic frequently finds the optimal or expected optimal solution in a fraction of the time required by implementations of simulated annealing, tabu search, and an exact partial enumeration method.