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 条

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

Rajesh, R. ;

Pugazhendhi, S. ;

Ganesh, K. .

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2012, 61 (5-8) :431-440

[32] An efficient simulated annealing algorithm for stochastic systems [J].

Alkhamis, Talal M. .

KUWAIT JOURNAL OF SCIENCE & ENGINEERING, 2006, 33 (02) :47-68

[33] An efficient population-based simulated annealing algorithm for 0–1 knapsack problem [J].

Nima Moradi ;

Vahid Kayvanfar ;

Majid Rafiee .

Engineering with Computers, 2022, 38 :2771-2790

[34] Approximation Algorithm for the Minimum Hub Cover Set Problem [J].

Trejo-Sanchez, Joel A. ;

Sansores-Perez, Candelaria E. ;

Garcia-Diaz, Jesus ;

Alberto Fernandez-Zepeda, Jose .

IEEE ACCESS, 2022, 10 :51419-51427

[35] An approximation of the minimum vertex cover in a graph [J].

Hiroshi Nagamochi ;

Toshihide Ibaraki .

Japan Journal of Industrial and Applied Mathematics, 1999, 16 :369-375

[36] An approximation of the minimum vertex cover in a graph [J].

Nagamochi, H ;

Ibaraki, T .

JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS, 1999, 16 (03) :369-375

[37] A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties [J].

Xiaofei LIU ;

Weidong LI ;

Jinhua YANG .

Frontiers of Computer Science, 2023, 17 (03) :128-135

[38] A primal-dual approximation algorithm for the k-prize-collecting minimum vertex cover problem with submodular penalties [J].

Liu, Xiaofei ;

Li, Weidong ;

Yang, Jinhua .

FRONTIERS OF COMPUTER SCIENCE, 2023, 17 (03)

[39] A Hybrid Algorithm with Simulated Annealing for the Maximum Clique Problem [J].

Zhang Zhijie .

JOURNAL OF COMPUTATIONAL AND THEORETICAL NANOSCIENCE, 2013, 10 (04) :1044-1047

[40] 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

← 1 2 3 4 5 →