Paper Info
Title
An improved simulated annealing algorithm for the maximum independent set problem
Abstract
The maximum independent set problem is a classic graph optimization problem. It is well known that it is an NP-Complete problem. In this paper, an improved simulated annealing algorithm is presented for the maximum independent set problem. In this algorithm, an acceptance function is defined for every vertex. This can help the algorithm find a near optimal solution to a problem. Simulations are performed on benchmark graphs and random graphs. The simulation results show that the proposed algorithm provides a high probability of finding optimal solutions.
Year
DOI
Venue
2006
10.1007/11816157_99
ICIC (1)
Keywords
Field
DocType
improved simulated annealing algorithm,optimal solution,high probability,benchmark graph,maximum independent set problem,near optimal solution,acceptance function,proposed algorithm,classic graph optimization problem,np-complete problem,random graph,maximum independent set,optimization problem,simulated annealing algorithm,np complete problem
Mathematical optimization,Out-of-kilter algorithm,Computer science,Algorithm,Matching (graph theory),Hopcroft–Karp algorithm,Adaptive simulated annealing,Independent set,Vertex cover,Feedback vertex set,Maximal independent set
Conference
Volume
ISSN
ISBN
4113
0302-9743
3-540-37271-7
Citations 
PageRank 
References 
4
0.41
16
Authors
3
Name
Order
Citations
PageRank
Xinshun Xu139032.51
Jun Ma21280127.50
Hua Wang3172.99