D.V. Andrade, M. G. C. Resende, and R.F. Werneck
J. of Heuristics, vol. 18, pp. 525-547, 2012.
ABSTRACT
Given
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.