M. G. C. Resende, T. A. Feo, and S. H. Smith
ACM Transactions on Mathematical Software, vol. 24, pp. 386-394, 1998
ABSTRACT
Let G = (V, E) be an undirected
graph, where V and E are the sets of vertices and edges of
G, respectively. A subset S of the vertices in V
is independent if all of its members are pairwise nonadjacent, i.e. have
no edge between them. A solution to the NP-hard maximum
independent set problem is an independent set of maximum cardinality.
This paper describes a set of FORTRAN subroutines to find an approximate
solution of a maximum independent set problem. A greedy randomized
adaptive search procedure (GRASP) is used to produce the
solutions. The design and implementation of the code are described
in detail, and computational experiments are reported, illustrating
solution quality as a function of running time.