A GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURE FOR MAXIMUM INDEPENDENTSET

Authors
FEO TA RESENDE MGC SMITH SH
Citation
Ta. Feo et al., A GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURE FOR MAXIMUM INDEPENDENTSET, Operations research, 42(5), 1994, pp. 860-878
Citations number
22
Categorie Soggetti
Management,"Operatione Research & Management Science","Operatione Research & Management Science
Journal title
Operations research → ACNP
ISSN journal
0030364X
Volume
42
Issue
5
Year of publication
1994
Pages
860 - 878
Database
ISI
SICI code
0030-364X(1994)42:5<860:AGRASP>2.0.ZU;2-N
Abstract
An efficient randomized heuristic for a maximum independent set is pre sented. The procedure is tested on randomly generated graphs having fr om 400 to 3,500 vertices and edge probabilities from 0.2 to 0.9. The h euristic can be implemented trivially in parallel and is tested on an MIMD computer with 1, 2, 4 and 8 processors. Computational results ind icate that the heuristic frequently finds the optimal or expected opti mal solution in a fraction of the time required by implementations of simulated annealing, tabu search, and an exact partial enumeration met hod.