CHN and Swap Heuristic to Solve the Maximum Independent Set Problem

Bouhouch Adil, Loqman Chakir, El Qadi Abderrahime

Abstract


We describe a new approach to solve the problem to find the maximum independent set in a given Graph, known also as Max-Stable set problem (MSSP). In this paper, we show how Max-Stable problem can be reformulated into a linear problem under quadratic constraints, and then we resolve the QP result by a hybrid approach based Continuous Hopfeild Neural Network (CHN) and Local Search. In a manner that the solution given by the CHN will be the starting point of the local search. The new approach showed a good performance than the original one which executes a suite of CHN runs, at each execution a new leaner constraint is added into the resolved model. To prove the efficiency of our approach, we present some computational experiments of solving random generated problem and typical MSSP instances of real life problem.


Keywords


CHN, combinatory problems, graph, independent set, local search, max-stable problem,

Full Text:

PDF


DOI: http://doi.org/10.11591/ijece.v7i6.pp3583-3592
Total views : 295 times


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

ISSN 2088-8708, e-ISSN 2722-2578