Algorithm 787 swMATH ID: 13182 Software Authors: Resende, Mauricio G.C.; Feo, Thomas A.; Smith, Stuart H. Description: 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. Homepage: http://dl.acm.org/citation.cfm?doid=293686.293690 Keywords: undirected graph Related Software: DIMACS; Algorithm 797; QUALEX; GRASP; TTTPLOTS; GRASP_QAP; PERL; BOINC; Algorithm 786; Algorithm 769; QAPLIB; MPI; PVM; OR-Library Cited in: 10 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year Algorithm 787: Fortran subroutines for approximate solution of maximum independent set problems using GRASP. Zbl 0956.68505Resende, Mauricio G. C.; Feo, Thomas A.; Smith, Stuart H. 1998 all top 5 Cited by 20 Authors 3 Resende, Mauricio G. C. 3 Ribeiro, Celso Carneiro 1 Abello, James M. 1 Aiex, Renata M. 1 Cung, Van-Dat 1 Feo, Thomas A. 1 Glover, Fred W. 1 Gupta, Ashok Kumar 1 Hoos, Holger H. 1 Ignatyev, Alexey A. 1 Marques-Silva, João P. 1 Martins, Simone L. 1 Morgado, António 1 Pardalos, Panos M. 1 Pullan, Wayne 1 Rosseti, Isabel 1 Roucairol, Catherine 1 Singh, Alok 1 Smith, Stuart H. 1 Vallejos, Reinaldo Cited in 5 Serials 3 Journal of Heuristics 1 ACM Transactions on Mathematical Software 1 Journal of Global Optimization 1 The Journal of Artificial Intelligence Research (JAIR) 1 Journal of Combinatorial Optimization Cited in 3 Fields 6 Computer science (68-XX) 6 Operations research, mathematical programming (90-XX) 2 Combinatorics (05-XX) Citations by Year