A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set

Abstract

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 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.