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] Mean analysis of an online algorithm for the vertex cover problem [J].

Birmele, Etienne ;

Delbot, Francois ;

Laforest, Christian .

INFORMATION PROCESSING LETTERS, 2009, 109 (09) :436-439

[22] SOLVING THE GENERALIZED VERTEX COVER PROBLEM BY GENETIC ALGORITHM [J].

Milanovic, Marija .

COMPUTING AND INFORMATICS, 2010, 29 (06) :1251-1265

[23] An approximation algorithm for the partial vertex cover problem in hypergraphs [J].

El Ouali, Mourad ;

Fohlin, Helena ;

Srivastav, Anand .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (02) :846-864

[24] An approximation algorithm for the partial vertex cover problem in hypergraphs [J].

Mourad El Ouali ;

Helena Fohlin ;

Anand Srivastav .

Journal of Combinatorial Optimization, 2016, 31 :846-864

[25] An effective algorithm for the minimum set cover problem [J].

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 hybridized tabu search approach for the minimum weight vertex cover problem [J].

Stefan Voß ;

Andreas Fink .

Journal of Heuristics, 2012, 18 :869-876

[27] A hybridized tabu search approach for the minimum weight vertex cover problem [J].

Voss, Stefan ;

Fink, Andreas .

JOURNAL OF HEURISTICS, 2012, 18 (06) :869-876

[28] Testing a simulated annealing algorithm in a classification problem [J].

Luebke, K ;

Weihs, C .

STOCHASTIC ALGORITHMS: FOUNDATIONS AND APPLICATIONS, 2003, 2827 :61-70

[29] Simulated annealing algorithm for balanced allocation problem [J].

R. Rajesh ;

S. Pugazhendhi ;

K. Ganesh .

The International Journal of Advanced Manufacturing Technology, 2012, 61 :431-440

[30] A simulated annealing algorithm for dynamic layout problem [J].

Baykasoglu, A ;

Gindy, NNZ .

COMPUTERS & OPERATIONS RESEARCH, 2001, 28 (14) :1403-1426

← 1 2 3 4 5 →