Cost Edge-Coloring of a Cactus - Engineering Information Institute

Articles

Cost Edge-Coloring of a Cactus [CET 2015]
Author(s)
Zhiqian Ye
ABSTRACT
Let C be a set of colors, and let w(c) be an integer cost assigned to a color c in C. An edge-coloring of a graph G = (V,E) is assigning a color in C to each edge e in E so that any two edges having end-vertex in common have different colors. The cost w(f) of an edge-coloring f of G is the sum of costs w(f(e)) of colors f(e) assigned to all edges e in G. An edge-coloring f of G is optimal if w(f) 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 frst polynomial-time algorithm to find an optimal edge-coloring of a cactus.
KEYWORDS
Cost Edge-Coloring, Cactus
References