A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set

Thomas A. Feo, Mauricio G. C. Resende and Stuart H. Smith
Additional contact information
Thomas A. Feo: The University of Texas at Austin, Austin, Texas
Mauricio G. C. Resende: AT&T Bell Laboratories, Murray Hill, New Jersey
Stuart H. Smith: Purdue University, West Lafayette, Indiana

Operations Research, 1994, vol. 42, issue 5, 860-878

Abstract: An efficient randomized heuristic for a maximum independent set is presented. The procedure is tested on randomly generated graphs having from 400 to 3,500 vertices and edge probabilities from 0.2 to 0.9. The heuristic can be implemented trivially in parallel and is tested on an MIMD computer with 1, 2, 4 and 8 processors. Computational results indicate that the heuristic frequently finds the optimal or expected optimal solution in a fraction of the time required by implementations of simulated annealing, tabu search, and an exact partial enumeration method.

Keywords: mathematics: combinatorics; networks/graphs: heuristics; programming: integer algorithms/heuristic (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (38)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.42.5.860 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:42:y:1994:i:5:p:860-878

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().