Algorithm 786: FORTRAN Subroutines for Approximate Solution of  Maximum Independent Set Problems using GRASP

M. G. C. Resende, T. A. Feo, and S. H. Smith

ACM Transactions on Mathematical Software, vol. 24, pp. 386-394, 1998


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.

PostScript file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 27 June 2002

Copyright Notice