WJET  Vol.3 No.3 C , October 2015
Cost Edge-Coloring of a Cactus
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.
Cite this paper: Ye, Z. , Li, Y. , Lu, H. and Zhou, X. (2015) Cost Edge-Coloring of a Cactus. World Journal of Engineering and Technology, 3, 119-134. doi: 10.4236/wjet.2015.33C018.

[1]   West, D.B. (2000) Introduction to Graph Theory. 2nd Edition, Prentice Hall, New Jersey.

[2]   Hajiabolhassan, H., Mehrabadi, M.L. and Tusserkani, R. (2000) Minimal Coloring and Strength of Graphs. Discrete Mathematics, 215, 265-270.

[3]   Mitchem, J., Morriss, P. and Schmeichel, E. (1997) On the Cost Chromatic Number of Outerplanar, Planar, and Line Graphs. Discussiones Mathematicae Graph Theory, 17, 229-241.

[4]   Giaro, K. and Kubale, M. (2000) Edge-Chromatic Sum of Trees and Bounded Cyclicity Graphs. Information Process- ing Letters, 75, 65-69.

[5]   Zhou, X. and Nishizeki, T. (2004) Algorithm for the Cost Edge-Coloring of Trees. J. Combinatorial Optimization, 8, 97-108.

[6]   Coffman, E.G., Garey, M.R., Johnson, D.S. and LaPaugh, A.S. (1985) Scheduling File Transfers. SIAM J. Computing, 14, 744-780.

[7]   Krawczyk, H. and Kubale, M. (1985) An Approximation Algorithm for Diagnostic Test Scheduling in Multicomputer Systems. IEEE Trans. Computers, 34, 869-872.

[8]   Marx, D. (2009) Complexity Results for Minimum Sum Edge Co-loring. Discrete Applied Mathematics, 157, 1034- 1045.

[9]   Goldberg, A.V. and Tarjan, R.E. (1987) Solving Minimum Cost Flow Problems by Successive Approximation. Proc. 19th ACM Symposium on the Theory of Computing, 7-18.

[10]   Goldberg, A.V. and Tar-jan, R.E. (1989) Finding Minimum-Cost Circulations by Canceling Negative Cycles. J. ACM, 36, 873-886.