Solving the fixed graph coloring problem by simulated annealing and greedy search

doi:10.1166/jctn.2015.3779

CORC > 北京大学 > 信息科学技术学院

	Solving the fixed graph coloring problem by simulated annealing and greedy search
	Zhao, Kai ; Geng, Xiutang ; Xu, Jin
刊名	journal of computational and theoretical nanoscience
	2015
DOI	10.1166/jctn.2015.3779
英文摘要	Local search techniques, such as simulated annealing and greedy search, have been used to solve various NP-hard problems, and it is well known that the graph coloring problem (GCP) is one of the most studied NP-hard optimization problems. In this paper, an adaptive local search algorithm is proposed to solve the GCP. The proposed algorithm is based on the standard simulated annealing technique, and makes the best of greedy search technique and search local strategy to speed up the convergence rate. Aim at the greedy search parameters, the run time for given benchmark instance, annealing temperature and its cool coefficient, adaptive control of the parameters and multistage simulated annealing are designed in order to improve quality-time trade-off of the proposed local search algorithm. As a result, our algorithm achieves a reasonable trade-off between computation time, solution quality, and complexity of implementation, and simulation results indicate that the proposed algorithm performs well on a set of 119 benchmark instances. Copyright ? 2015 American Scientific Publishers All rights reserved.; SCI(E); EI; 0; ARTICLE; 4; 637-646; 12
语种	英语
内容类型	期刊论文
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/329249]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Zhao, Kai,Geng, Xiutang,Xu, Jin. Solving the fixed graph coloring problem by simulated annealing and greedy search[J]. journal of computational and theoretical nanoscience,2015.
APA	Zhao, Kai,Geng, Xiutang,&Xu, Jin.(2015).Solving the fixed graph coloring problem by simulated annealing and greedy search.journal of computational and theoretical nanoscience.
MLA	Zhao, Kai,et al."Solving the fixed graph coloring problem by simulated annealing and greedy search".journal of computational and theoretical nanoscience (2015).