An approximate algorithm for the cost total-coloring of trees
Yong Chen · Journal of Shandong University · 2006
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Δ~2) if n is the number of vertices and Δ is the maximum degree(of T).