期刊名称：International Journal on Computer Science and Engineering
印刷版ISSN：2229-5631
电子版ISSN：0975-3397
出版年度：2010
卷号：2
期号：6
页码：2071-2077
出版社：Engg Journals Publications
摘要：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.
关键词：maximum stable set problem; quadratic 0-1 programming; continuous Hopfield network
