Fast local search for the maximum independent set problem

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.


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.

PDF file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 12 June 2008

Copyright Notice