A GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURE FOR MAXIMUM INDEPENDENT SET
成果类型：
Article
署名作者：
FEO, TA; RESENDE, MGC; SMITH, SH
署名单位：
AT&T; Nokia Corporation; Nokia Bell Labs; Purdue University System; Purdue University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.42.5.860
发表日期：
1994
页码：
860-878
关键词：
摘要：
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.