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 条

[41] A heuristic simulated annealing algorithm for the circular packing problem [J].

Liu, Jingfa ;

Zheng, Yu ;

Liu, Wenjie .

THIRD INTERNATIONAL CONFERENCE ON GENETIC AND EVOLUTIONARY COMPUTING, 2009, :802-805

[42] Permutation Algorithm with Simulated Annealing for Laser Antimissile Problem [J].

Sun, Yong ;

Zhang, Maorui ;

Liu, Weiwei ;

Li, He ;

Zhang, Lina .

FRONTIERS OF MANUFACTURING AND DESIGN SCIENCE, PTS 1-4, 2011, 44-47 :265-+

[43] A modified simulated annealing algorithm for the quadratic assignment problem [J].

Misevicius, A .

INFORMATICA, 2003, 14 (04) :497-514

[44] A Simulated Annealing Algorithm to the Stochastic Network Interdiction Problem [J].

Janjarassuk, U. ;

Nakrachata-Amon, T. .

2015 IEEE INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT (IEEM), 2015, :230-233

[45] Simulated annealing algorithm for the robust spanning tree problem [J].

Nikulin, Yury .

JOURNAL OF HEURISTICS, 2008, 14 (04) :391-402

[46] A fast simulated annealing algorithm for the examination timetabling problem [J].

Leite, Nuno ;

Melicio, Fernando ;

Rosa, Agostinho C. .

EXPERT SYSTEMS WITH APPLICATIONS, 2019, 122 :137-151

[47] A Simulated Annealing Algorithm for the Generalized Quadratic Assignment Problem [J].

Mckendall, Alan ;

Dhungel, Yugesh .

ALGORITHMS, 2024, 17 (12)

[48] New Simulated Annealing Algorithm for Quadratic Assignment Problem [J].

Ghandeshtani, Kambiz Shojaee ;

Mollai, Nima ;

Seyedkashi, Seyed Mohammad Hosein ;

Neshati, Mohammad Mohsen .

PROCEEDINGS OF THE FOURTH INTERNATIONAL CONFERENCE ON ADVANCED ENGINEERING COMPUTING AND APPLICATIONS IN SCIENCES (ADVCOMP 2010), 2010, :87-92

[49] A Hybrid Simulated Annealing Algorithm for Container Loading Problem [J].

Peng, Yu ;

Zhang, Defu ;

Chin, Francis Y. L. .

WORLD SUMMIT ON GENETIC AND EVOLUTIONARY COMPUTATION (GEC 09), 2009, :919-922

[50] A simulated annealing algorithm for the maximum planar subgraph problem [J].

Poranen, T .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2004, 81 (05) :555-568

← 1 2 3 4 5 →