| 关于图染色的算法 |
| |
| 引用本文： | 马建峰.关于图染色的算法[J].陕西师范大学学报,1989(2). |
| |
| 作者姓名： | 马建峰 |
| |
| 作者单位： | 陕西师范大学计算机科学系 |
| |
| 摘 要： | 本文给出了图上顶点染色,边染色的算法.其中边染色算法是一个非多项式时间的精确算法,该算法是先求出所有极大匹配,然后再求极小匹配覆盖,最后得出最优边染色.顶点染色算法是一个多项式时间的近似算法,该算法的时间复杂性为O(n~3logn),空间复杂性为O(n~3)的近似算法,它是由贪吃策略得到的.对于任意的图,该算法所用的期望颜色数为「log(n 1)」.
|
| 关 键 词： | 图染色 多项式时间算法 非多项式时间算法 时间复杂性 空间复杂性 |
Graph Coloring Algorithm |
| |
| Ma Jianfeng.Graph Coloring Algorithm[J].Journal of Shaanxi Normal University: Nat Sci Ed,1989(2). |
| |
| Authors: | Ma Jianfeng |
| |
| Institution: | Department of Computer Science |
| |
| Abstract: | In this paper, vertex coloring algorithm and edge coloring algorithms of the graph are given. Edge coloring algorithm is a non-polynomial time precise algorithm, the procedure of which works as follows: first, find all maximum matchings, then derive minimum edge-covering by matchings, finally obtain optimal edge coloring. Vertex coloring algorithm is a polynomial time approximate one which is obtained by using the greedy tactics. For any graph,its time complexity is O(n~3 logn), its space complexity is O(n~3), its expected chromatic number islog(n 1)]. |
| |
| Keywords: | graph coloring polynomial time algorithm non-polynomial time algorithm time complexity space complexity |
| 本文献已被 CNKI 等数据库收录！ |
|
