|
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
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E87-D
No.2
pp.337-342 Publication Date: 2004/02/01 Online ISSN:
DOI: Print ISSN: 0916-8532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science) Category: Keyword: cost total coloring, dynamic programming, matching, total coloring, tree,
Full Text: PDF>>
Summary:
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.
|
|
|