
For FullText 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 EdgeColorings of Trees Can Be Reduced to Matchings
Takehiro ITO Naoki SAKAMOTO Xiao ZHOU Takao NISHIZEKI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E94D
No.2
pp.190195 Publication Date: 2011/02/01
Online ISSN: 17451361
DOI: 10.1587/transinf.E94.D.190
Print ISSN: 09168532 Type 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 edgecoloring, multitree, perfect matching, tree,
Full Text: PDF>>
Summary:
Let C be a set of colors, and let ω(c) be an integer cost assigned to a color c in C. An edgecoloring 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 edgecoloring f of G is the sum of costs ω(f(e)) of colors f(e) assigned to all edges e in G. An edgecoloring f of G is optimal if ω(f) is minimum among all edgecolorings of G. In this paper, we show that the problem of finding an optimal edgecoloring 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 edgecoloring of T in time O(n^{1.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.

