An unconstrained binary quadratic programming for the maximum independent set problem
Articles
Sidi Mohamed Douiri
University Mohammed V-Agdal, Morocco
Souad Elbernoussi
University Mohammed V-Agdal, Morocco
Published 2012-10-25
https://doi.org/10.15388/NA.17.4.14047
PDF

Keywords

maximum independent set

How to Cite

Douiri S. M. and Elbernoussi S. (2012) “An unconstrained binary quadratic programming for the maximum independent set problem”, Nonlinear Analysis: Modelling and Control, 17(4), pp. 410-417. doi: 10.15388/NA.17.4.14047.

Abstract

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.

PDF
Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Please read the Copyright Notice in Journal Policy