树的费用全染色的近似算法

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

An approximate algorithm for the cost total-coloring of trees

Let G be a simple graph, C be a set of colors, and let w be a cost function which assigns a real number w(c) to each color c in C. A total coloring of a graph G is to color all the elements of V(G)∪E(G) in such a way that no two adjacent or incident elements receive the same color. A 2-approximate algorithm is given to find an optimal cost total-coloring of a given tree T, that is, a total coloring f of　T such that the sum of costs w(f(x)) of　colors f(x) assigned to all elements x is minimum among all total- colorings of T. The algorithm takes time O(nΔ²) if n is the number of vertices and Δ is the maximum degree of T.