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
Mauricio G.C. Resende's Home PageLast modified: 12 June 2008