An unconstrained binary quadratic programming for the maximum independent set problem - Douiri, Sidi Mohamed Mohamed; Elbernoussi, Souad (Nonlinear Analysis: Modelling and Control, 2012)
For a given graph G = (V, E) the maximum independent set problem is to find the largest subset of pairwise nonadjacent vertices. We propose a new model which is a reformulation of the maximum independent set problem as an unconstrained quadratic binary programming, and we resolve it afterward by means of a genetic algorithm. The efficiency of the approach is confirmed by results of numerical experiments on DIMACS benchmarks.
Keywords: maximum independent set