摘要
图着色问题是NP -难度的问题。基于两种传统的启发式算法 ,提出了两种新的求解策略 ,由此给出了求图着色问题的两个新算法。与传统算法相比 ,其中一个新算法在时间复杂度不变的条件下 ,解的质量有明显提高 ;另一个则在时间复杂度稍有增加的前提下 ,进一步较显著地提高了所得解的质量。
The Graph Coloring Problem (GCP) is NP-hard.Analyzing two well-known heuristic algorithms,the paper proposes two novel strategies for solving GCP,and gives two new heuristic algorithms for GCP based these strategies.Experimental results show one algorithm outperforms these two known algorithms and the other greatly improves on the quality of solutions with a little higher time complexity.
出处
《微计算机应用》
2004年第4期391-395,共5页
Microcomputer Applications
基金
国家自然科学基金资助项目 (10 2 0 10 0 9)
广东省自然科学基金资助项目 (0 2 10 72 )
关键词
图着色问题
算法
启发式算法
NP问题
graph coloring,NP-hardness,time complexity,heuristic algorithm
