Algorithm 787

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 vertices and edges of G, respectively. A subset of the vertices S⊆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 describes gmis, 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 algorithm is described in detail. Implementation and usage of the package is outlined, and computational experiments are reported, illustrating solution quality as a function of running time.

This software is also peer reviewed by journal TOMS.

References in zbMATH (referenced in 11 articles , 1 standard article )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Ignatiev, Alexey; Morgado, Antonio; Marques-Silva, Joao: On reducing maximum independent set to minimum satisfiability (2014)
  2. Ribeiro, Celso C.; Rosseti, Isabel; Vallejos, Reinaldo: Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms (2012)
  3. Araujo, Filipe; Farinha, Jorge; Domingues, Patricio; Silaghi, Gheorghe Cosmin; Kondo, Derrick: A maximum independent set approach for collusion detection in voting pools (2011)
  4. Pullan, Wayne: Phased local search for the maximum clique problem (2006)
  5. Pullan, W.; Hoos, H.H.: Dynamic local search for the maximum clique problem (2006)
  6. Singh, Alok; Gupta, Ashok Kumar: A hybrid heuristic for the maximum clique problem (2006)
  7. Glover, Fred: Tutorial on surrogate constraint approaches for optimization in graphs (2003)
  8. Aiex, Renata M.; Resende, Mauricio G.C.; Ribeiro, Celso C.: Probability distribution of solution time in GRASP: an experimental investigation (2002)
  9. Cung, Van-Dat; Martins, Simone L.; Ribeiro, Celso C.; Roucairol, Catherine: Strategies for the parallel implementation of metaheuristics (2002)
  10. Abello, J.; Pardalos, P.M.; Resende, M.G.C.: On maximum clique problems in very large graphs (1999)
  11. Resende, Mauricio G.C.; Feo, Thomas A.; Smith, Stuart H.: Algorithm 787: Fortran subroutines for approximate solution of maximum independent set problems using GRASP (1998)