树的费用全染色的近似算法 (2006年)

给定无向简单图G=（V，E）与颜色集C，并且对C中的每一种颜色c设定一个费用值w（c）∈R+。全染色是给出图的一个可行染色使得相关联的边和点、相邻的点或边都染不同的颜色。定义了费用全染色问题，即求解最优的全染色f，使得染色费用和∑w（f（x））最小。对于树图T，给出了一个2-近似算法，该算法的运行时间x∈V（G）∪E（C）为O（n△2）。