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 条
  • [21] An approximation algorithm for the partial vertex cover problem in hypergraphs
    El Ouali, Mourad
    Fohlin, Helena
    Srivastav, Anand
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (02) : 846 - 864
  • [22] An approximation algorithm for the partial vertex cover problem in hypergraphs
    Mourad El Ouali
    Helena Fohlin
    Anand Srivastav
    Journal of Combinatorial Optimization, 2016, 31 : 846 - 864
  • [23] Mean analysis of an online algorithm for the vertex cover problem
    Birmele, Etienne
    Delbot, Francois
    Laforest, Christian
    INFORMATION PROCESSING LETTERS, 2009, 109 (09) : 436 - 439
  • [24] A hybridized tabu search approach for the minimum weight vertex cover problem
    Stefan Voß
    Andreas Fink
    Journal of Heuristics, 2012, 18 : 869 - 876
  • [25] An effective algorithm for the minimum set cover problem
    Zhang, Pei
    Wang, Rong-Long
    Wu, Chong-Guang
    Okazaki, Kozo
    PROCEEDINGS OF 2006 INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND CYBERNETICS, VOLS 1-7, 2006, : 3032 - +
  • [26] A simulated annealing algorithm for dynamic layout problem
    Baykasoglu, A
    Gindy, NNZ
    COMPUTERS & OPERATIONS RESEARCH, 2001, 28 (14) : 1403 - 1426
  • [27] Simulated annealing algorithm for balanced allocation problem
    R. Rajesh
    S. Pugazhendhi
    K. Ganesh
    The International Journal of Advanced Manufacturing Technology, 2012, 61 : 431 - 440
  • [28] Testing a simulated annealing algorithm in a classification problem
    Luebke, K
    Weihs, C
    STOCHASTIC ALGORITHMS: FOUNDATIONS AND APPLICATIONS, 2003, 2827 : 61 - 70
  • [29] A hybridized tabu search approach for the minimum weight vertex cover problem
    Voss, Stefan
    Fink, Andreas
    JOURNAL OF HEURISTICS, 2012, 18 (06) : 869 - 876
  • [30] Simulated annealing algorithm for balanced allocation problem
    Rajesh, R.
    Pugazhendhi, S.
    Ganesh, K.
    INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2012, 61 (5-8) : 431 - 440
12345