Thomas A. Feo,Mauricio G.C. Resende, and Stuart H. Smith
Operations Research, vol. 42, pp. 860-878, 1994
ABSTRACT
An efficient randomized heuristic for maximum
independent set is presented. The procedure is tested on randomly
generated graphs having from 400 to 3500 vertices and edge probabilities
from 0.2 to 0.9. The heuristic can be trivially implemented in
parallel and is tested on an 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.
PDF file of full paper
Go back
Mauricio G.C. Resende's Home PageLast modified: 14 March 2008