Cost Edge-Coloring of a Cactus

Abstract Full-Text HTML XML Download as PDF (Size:662KB) PP. 119-134

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.

Conflicts of Interest

The authors declare no conflicts of interest.

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. http://dx.doi.org/10.1016/S0012-365X(99)00319-2 [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. http://dx.doi.org/10.7151/dmgt.1050 [4] Giaro, K. and Kubale, M. (2000) Edge-Chromatic Sum of Trees and Bounded Cyclicity Graphs. Information Process- ing Letters, 75, 65-69. http://dx.doi.org/10.1016/S0020-0190(00)00072-7 [5] Zhou, X. and Nishizeki, T. (2004) Algorithm for the Cost Edge-Coloring of Trees. J. Combinatorial Optimization, 8, 97-108. http://dx.doi.org/10.1023/B:JOCO.0000021940.40066.0c [6] Coffman, E.G., Garey, M.R., Johnson, D.S. and LaPaugh, A.S. (1985) Scheduling File Transfers. SIAM J. Computing, 14, 744-780. http://dx.doi.org/10.1137/0214054 [7] Krawczyk, H. and Kubale, M. (1985) An Approximation Algorithm for Diagnostic Test Scheduling in Multicomputer Systems. IEEE Trans. Computers, 34, 869-872. http://dx.doi.org/10.1109/TC.1985.1676647 [8] Marx, D. (2009) Complexity Results for Minimum Sum Edge Co-loring. Discrete Applied Mathematics, 157, 1034- 1045. http://dx.doi.org/10.1016/j.dam.2008.04.002 [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. http://dx.doi.org/10.1145/28395.28397 [10] Goldberg, A.V. and Tar-jan, R.E. (1989) Finding Minimum-Cost Circulations by Canceling Negative Cycles. J. ACM, 36, 873-886. http://dx.doi.org/10.1145/76359.76368