Algorithm 787: Fortran subroutines for approximate solution of maximum independent set problems using GRASP

Let G = (V, E) be an undirected graph, where V and E are the sets of vertic es and edges of G, respectively. A subset of the vertices S subset of or eq ual to 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 article des cribes gmis, a set of Fortran subroutines to find an approximate solution o f a maximum independent set problem. A greedy randomized adaptive search pr ocedure (GRASP) is used to produce the solutions. The algorithm is describe d in detail. Implementation and usage of the package is outlined, and compu tational experiments are reported, illustrating solution quality as a funct ion of running time.