Fast local search for the maximum independent set problem
D.V. Andrade, M.
G. C. Resende, and R.F. Werneck
J. of Heuristics, vol. 18, pp. 525-547, 2012.
a graph G = (V,E), the independent set problem is that of finding a
maximum-cardinality subset S of V such that no two vertices in S are
adjacent. We introduce two fast local search routines for this problem.
The first can determine in linear time whether a maximal solution can
be improved by replacing a single vertex with two others. The second
routine can determine in O(mD) time (where D is the highest degree in
the graph) whether there are two solution vertices than can be replaced
by a set of three. We also present a more elaborate heuristic that
successfully applies local search to find near-optimum solutions to a
wide variety of instances. We test our algorithms on instances from the
literature as well as on new ones proposed in this paper.
PDF file of full paper
Resende's Home Page
Last modified: 2- July 2012