关于图染色的算法 (1989年)

时间:2024-06-19 12:27:59
【文件属性】:

文件名称:关于图染色的算法 (1989年)

文件大小:755KB

文件格式:PDF

更新时间:2024-06-19 12:27:59

自然科学 论文

本文给出了图上顶点染色,边染色的算法.其中边染色算法是一个非多项式时间的精确算法,该算法是先求出所有极大匹配,然后再求极小匹配覆盖,最后得出最优边染色.顶点染色算法是一个多项式时间的近似算法,该算法的时间复杂性为O(n~3logn),空间复杂性为O(n~3)的近似算法,它是由贪吃策略得到的.对于任意的图,该算法所用的期望颜色数为「log(n+1)」.


网友评论