For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Cost Total Colorings of Trees
Shuji ISOBE Xiao ZHOU Takao NISHIZEKI
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2004/02/01
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
cost total coloring, dynamic programming, matching, total coloring, tree,
Full Text: PDF(245.6KB)
>>Buy this Article
A total coloring of a graph G is to color all vertices and edges of G so that no two adjacent or incident elements receive the same color. Let C be a set of colors, and let ω be a cost function which assigns to each color c in C a real number ω(c) as a cost of c. A total coloring f of G is called an optimal total coloring if the sum of costs ω(f(x)) of colors f(x) assigned to all vertices and edges x is as small as possible. In this paper, we give an algorithm to find an optimal total coloring of any tree T in time O(nΔ3) where n is the number of vertices in T and Δ is the maximum degree of T.