2010 | OriginalPaper | Chapter
Minimum Cost Edge-Colorings of Trees Can Be Reduced to Matchings
Authors : Takehiro Ito, Naoki Sakamoto, Xiao Zhou, Takao Nishizeki
Published in: Frontiers in Algorithmics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
, 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.