A new motion equation for the minimum vertex cover problem

被引：2

作者：

Xu, XS ^{[1
]}

Tang, Z

Wang, RL

Wang, XG

机构：

[1] Toyama Univ, Fac Engn, Toyama 9308555, Japan

[2] Univ Fukui, Fac Engn, Fukui 9108507, Japan

来源：

NEUROCOMPUTING | 2004年 / 56卷

关键词：

vertex cover; NP-complete problem; Hopfield neural network; local minimum;

D O I：

10.1016/j.neucom.2003.08.004

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

The minimum vertex cover problem is a classic graph optimization problem. It is well known that it is an NP-complete problem. In this paper, a new motion equation with a special term of the Hopfield neural network is presented for the minimum vertex cover problem. Extensive simulations are performed, and the simulation results show that the Hopfield neural network with the new motion equation works much better than the original Hopfield network and a sequential ratio-2 algorithm on random graphs, and has higher convergence rate to optimal solutions for benchmark graphs. (C) 2003 Elsevier B.V. All rights reserved.

引用

页码：441 / 446

页数：6

共 8 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

DEHNE F, SOLVING LARGE FPT PR

[3] FIXED-PARAMETER TRACTABILITY AND COMPLETENESS .2. ON COMPLETENESS FOR W[1] [J].