Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Minimum Cost Edge-Colorings of Trees Can Be Reduced to Matchings
verfasst von : Takehiro Ito, Naoki Sakamoto, Xiao Zhou, Takao Nishizeki
Erschienen in: Frontiers in Algorithmics
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.