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.
 Minimum Cost Edge-Colorings of Trees Can Be Reduced to MatchingsTakehiro ITO  Naoki SAKAMOTO  Xiao ZHOU  Takao NISHIZEKI  Publication IEICE TRANSACTIONS on Information and Systems   Vol.E94-D   No.2   pp.190-195Publication Date: 2011/02/01 Online ISSN: 1745-1361 DOI: 10.1587/transinf.E94.D.190 Print ISSN: 0916-8532Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science -- Mathematical Foundations and Applications of Algorithms and Computer Science --)Category: Keyword: algorithm,  cost edge-coloring,  multitree,  perfect matching,  tree,  Full Text: PDF(538.5KB)>>Buy this Article Summary:  Let C be a set of colors, and let ω(c) be an integer cost assigned to a color c in C. An edge-coloring of a graph G is to color all the edges of G so that any two adjacent edges are colored with different colors in C. The cost ω(f) of an edge-coloring f of G is the sum of costs ω(f(e)) of colors f(e) assigned to all edges e in G. An edge-coloring f of G is optimal if ω(f) is minimum among all edge-colorings of G. In this paper, we show that the problem of finding an optimal edge-coloring of a tree T can be simply reduced in polynomial time to the minimum weight perfect matching problem for a new bipartite graph constructed from T. The reduction immediately yields an efficient simple algorithm to find an optimal edge-coloring of T in time O(n1.5Δlog(nNω)), where n is the number of vertices in T, Δ is the maximum degree of T, and Nω is the maximum absolute cost |ω(c)| of colors c in C. We then show that our result can be extended for multitrees.