| 求图着色问题的新算法 |
| |
| 引用本文： | 陈卫东. 求图着色问题的新算法[J]. 微计算机应用, 2004, 25(4): 391-395 |
| |
| 作者姓名： | 陈卫东 |
| |
| 作者单位： | 华南师范大学计算机系,广州,510631 |
| |
| 基金项目： | 国家自然科学基金资助项目 (10 2 0 10 0 9)，广东省自然科学基金资助项目 (0 2 10 72 ) |
| |
| 摘 要： | 图着色问题是NP-难度的问题。基于两种传统的启发式算法，提出了两种新的求解策略，由此给出了求图着色问题的两个新算法。与传统算法相比，其中一个新算法在时间复杂度不变的条件下，解的质量有明显提高；另一个则在时间复杂度稍有增加的前提下，进一步较显著地提高了所得解的质量。
|
| 关 键 词： | 图着色问题 算法 启发式算法 NP问题 |
New Algorithms for Graph Coloring Problem |
| |
| CHEN Weidong. New Algorithms for Graph Coloring Problem[J]. Microcomputer Applications, 2004, 25(4): 391-395 |
| |
| Authors: | CHEN Weidong |
| |
| Abstract: | 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. |
| |
| Keywords: | graph coloring NP-hardness time complexity heuristic algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
