Paper Info
Title
Algorithm 787: Fortran subroutines for approximate solution of maximum independent set problems using GRASP
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 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.
Year
DOI
Venue
1998
10.1145/293686.293690
ACM Trans. Math. Softw.
Keywords
DocType
Volume
grasp,maximum independent set problem,fortran subroutine,computational experiment,pairwise nonadjacent,combinatorial optimization,greedy randomized adaptive search,maximum independent set,np-hard maximum independent set,illustrating solution quality,approximate solution,fortran subroutines,maximum cardinality,independent set,maximum clique,local search,computer experiment,greedy randomized adaptive search procedure
Journal
24
Issue
ISSN
Citations 
4
0098-3500
14
PageRank 
References 
Authors
1.09
4
3
Name
Order
Citations
PageRank
Mauricio G. C. Resende13729336.98
Thomas A. Feo216323.88
Stuart H. Smith3141.09