TITLE:
Cost Edge-Coloring of a Cactus
AUTHORS:
Zhiqian Ye, Yiming Li, Huiqiang Lu, Xiao Zhou
KEYWORDS:
Cactus, Cost Edge-Coloring, Minimum Cost Maximum Flow Problem
JOURNAL NAME:
World Journal of Engineering and Technology,
Vol.3 No.3C,
October
22,
2015
ABSTRACT:
Let C be a set of colors, and let
be an integer cost
assigned to a color c in C. An edge-coloring of a graph
is assigning a color
in C to each edge
so that any two edges
having end-vertex in common have different colors. The cost
of an edge-coloring f
of G is the sum of costs
of colors
assigned to all edges e
in G. An edge-coloring f of G is optimal if
is minimum among all
edge-colorings of G. A cactus is a connected graph in which every block is
either an edge or a cycle. In this paper, we give an algorithm to find an
optimal edge- coloring of a cactus in
polynomial time. In our best knowledge, this is the first polynomial-time
algorithm to find an optimal edge-coloring of a cactus.