An efficient simulated annealing algorithm for the minimum vertex cover problem

被引：20
|
作者：
Xu, XS [1 ]
Ma, J [1 ]
机构：
[1] Shandong Univ, Sch Comp Sci & Technol, Shandong 250061, Peoples R China
来源：
NEUROCOMPUTING | 2006年 / 69卷 / 7-9期
关键词：
vertex cover; NP-complete problem; simulated annealing; local minimum;
D O I：
10.1016/j.neucom.2005.12.016
中图分类号：
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, an efficient simulated annealing algorithm is presented for the minimum vertex cover problem. In this algorithm, an acceptance function is defined for every vertex. This can help the algorithm in finding a near-optimal solution to a problem. Simulations are performed on several benchmark graphs, and the simulation results show that the proposed algorithm provides a high probability of finding optimal solutions. (c) 2006 Elsevier B.V. All rights reserved.
引用
收藏
页码：913 / 916
页数：4
相关论文
共 50 条
  • [1] An Exact Algorithm for Minimum Vertex Cover Problem
    Wang, Luzhi
    Hu, Shuli
    Li, Mingyang
    Zhou, Junping
    MATHEMATICS, 2019, 7 (07)
  • [2] Clever Steady Strategy Algorithm: A simple and efficient approximation algorithm for minimum vertex cover problem
    Fayaz, Muhammad
    Arshad, Shakeel
    2015 13TH INTERNATIONAL CONFERENCE ON FRONTIERS OF INFORMATION TECHNOLOGY (FIT), 2015, : 277 - 282
  • [3] A new motion equation for the minimum vertex cover problem
    Xu, XS
    Tang, Z
    Wang, RL
    Wang, XG
    NEUROCOMPUTING, 2004, 56 : 441 - 446
  • [4] The Minimum Generalized Vertex Cover Problem
    Hassin, Refael
    Levin, Asaf
    ACM TRANSACTIONS ON ALGORITHMS, 2006, 2 (01) : 66 - 78
  • [5] An Hopfield network learning for minimum vertex cover problem
    Chen, XM
    Tang, Z
    Xu, XS
    Li, SS
    Xia, GP
    Zong, ZL
    Wang, JH
    SICE 2004 ANNUAL CONFERENCE, VOLS 1-3, 2004, : 1150 - 1155
  • [6] New Heuristic Algorithm for Unweighted Minimum Vertex Cover
    Ugurlu, Onur
    2012 IV INTERNATIONAL CONFERENCE PROBLEMS OF CYBERNETICS AND INFORMATICS (PCI), 2012,
  • [7] Stochastic minimum weight vertex cover problem
    Ni, Yaodong
    Proceedings of the Fifth International Conference on Information and Management Sciences, 2006, 5 : 358 - 364
  • [8] Cellular Learning Automata Based Algorithm for Solving Minimum Vertex Cover Problem
    Mousavian, Aylin
    Rezvanian, Alireza
    Meybodi, Mohammad Reza
    2014 22nd Iranian Conference on Electrical Engineering (ICEE), 2014, : 996 - 1000
  • [9] An efficient exact algorithm for constraint bipartite vertex cover
    Fernau, H
    Niedermeier, R
    JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2001, 38 (02): : 374 - 410
  • [10] Crown reductions for the minimum weighted vertex cover problem
    Chlebik, Miroslav
    Chlebikkova, Janka
    DISCRETE APPLIED MATHEMATICS, 2008, 156 (03) : 292 - 312
12345