ABSTRACT

A large number of problems in artificial intelligence and other areas of computer science can be viewed as special cases of the Maximum Stable Set Problem (MSSP). In this paper, we propose a new approach to solve the MSSP problem using the continuous Hopfield network (CHN). The proposed method is divided into two steps: the first one involves modeling the MSSP problem as a 0-1 quadratic programming, and solving this model via the CHN which rapidly gives a local minimum. The second step concerns improving the initial solution by adding a linear constraint to the first model; then, we use the CHN to solve the obtained model. We prove that this approach is able to determine a good solution of the MSSP problem. To test the theoretical results, some computational experiments solving the MSSP problem are shown.