D.V. Andrade, M. G. C. Resende and R.F. Werneck
Proceedings of 7th International Workshop on Experimental Algorithms (WEA 2008), C.C. McGeoch (Eds.), LNCS, Springer, vol. 5038, pp. 220-234, 2008.
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 present a fast local search routine for this problem. Our algorithm can determine in linear time if a maximal solution can be improved by replacing a single vertex with two others. We also show that an incremental version of this method can be useful within more elaborate heuristics. We test our algorithms on instances from the literature as well as on new ones proposed in this paper.
Last modified: 12 June 2008